Test (77) 썸네일형 리스트형 [Swift] Dynamic Programming (동적 계획법) DP(Dynamic Programming; 동적 계획법)큰 문제를 작은 문제로 쪼개어 푸는 알고리즘 기법으로 이미 계산한 작은 문제의 정답을 저장(메모이제이션) 해 두고, 필요할 떄 재사용하여 중복 계산을 방지해서 효율적이다. 대표적으로 경로탐색, 최적화(최대/최소/방법 수), 조합 문제 등에서 사용할 수 있다.대표적인 예로 피보나치 수열을 풀어볼려고 한다. 우선 기존에는 대표적인 재귀함수 문제로 재귀함수로 코드를 구현했다.func fibRecursive(_ n: Int) -> Int { if n 이것도 문제를 풀 수 있지만 n이 커지면 연산량이 많아지고, 현재 같은 계산을 계속 반복하고 있어 시간이 오래 걸린다.연산을 했던 것을 저장하여 저장된 것이 있다면 꺼내서 사용하는 DP 알고리즘으로 구현.. [Swift] BFS (너비 우선 탐색) BFS(너비 우선 탐색) 시작 정점을 방문 한 후 시작정점에 인접한 모든 정점들을 우선 방문한다. DFS와 다른 점은 DFS는 탐색하기 위해 원소를 최대한 깊게 따라가야하지만 BFS는 현재 인접한 노드를 먼저 방문해야한다. 이것은 인접한 노드 중 방문하지 않은 모든 노드를 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. 이것은 FIFO(First In First Out) 구조를 가진 큐를 이용하면 된다. func bfs(graph: [Int: [Int]], startNode: Int) -> [Int] { var visited: [Int] = [] var queue: [Int] = [startNode] while !queue.isEmpty { let curr.. [Swift] DFS(깊이 우선 탐색) DFS(깊이 우선 탐색) DFS(Depth-First Search)는 트리나 그래프 구조에서 하나의 경로를 가능한 깊게 먼저 탐색한 후 다른 경로로 이동하는 알고리즘 이다.갈 수 있는 만큼 계속 탐색하다가 갈 수 없게 된다면, 다른 방향으로 다시 탐지하는 구조이다. 이 구조는 LIFO(Last In Frist Out) 구조인 Stack과 같다. 이 코드를 Swift로 구현해보았다. 쉽게 이해해서 방문하지 않은 곳은 계속 찾아가면 된다. func dfs(graph: [Int: [Int]], currentNode: Int) -> [Int] { var visited: [Int] = [] var willVisit: [Int] = [currentNode] for node in graph[c.. [CS] 그래프(Graph) 그래프(Graph)그래프는 노드(정점, Vertex)와 간선(edge)으로 구성된 비선형 자료 구조이다. 복잡하게 연결된 객체 간의 관계를 표현할 때 사용한다. 아래는 그래프에서 사용하는 용어들이다.노드(Node) : 연결 관계를 가진 각 데이터를 의미, 정점(Vertext)라고도 한다.간선(Edge) : 노드 간의 관계를 표시한 선인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점) 무방향(Undirected) vs 양방향(Directed)그래프에는 무방향 그래프와 유방향 그래프가 있다. 무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖고 있고, 유방향 그래프(Directed Graph)는 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각.. [Swift] 힙(Heap) 힙(Heap)힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 구조이다.부모의 값은 항상 자식들의 값보다 크거나(Max Heap), 항상 자식들의 값보다 작거나(Min Heap)이여야 한다. 아래는 Max Heap을 구현해 보았다.public struct MaxHeap { public private(set) var elements: [T] = [] public init() {} public mutating func insert(_ element: T) { elements.append(element) var i = elements.count - 1 while i > 0 { .. [CS] 트리 / 이진 트리(Binary Tree) / 완전 이진 트리(Complete Binary Tree) 트리 (Tree)트리 구조(Tree)란 그래프의 일종으로, 한 노드에서 시작해서 다른 저엄드을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 트리는 계층형 비선형구조이다. 여기서 비선형 구조란 선형 구조와 다르게 데이터가 계층 혹은 망으로 구성되어 있다. 아래는 트리에서 사용하는 용어이다. Node : 트리에서 데이터를 저장하는 요소Level : 최상위 노드를 Level0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이로 표현Root Node : 트리 최상단 Level에 있는 노드Parent Node: 어떤 노드의 상위 레벨에 연결된 노드Child Node: 어떤 노드의 하위 레벨에 연결된 노드Leaf Node : Child Node가 없는 노드Sibling Node : 동일한 .. [Swift] 큐(Queue) 큐(Queue)는 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 큐의 기능은 다음과 같다.enqueue(data) : 맨 뒤 데이터 추가하기dequeue() : 맨 앞 데이터 뽑기isEmpty() : 큐가 비었는지 안 비었는지 여부 조회Swift에서 아래와 같이 구현하면 사용할 수 있다.struct Queue{ private var queue: [T] = [] var count: Int{ return queue.count } // 데이터 추가 mutating func enqueue(_ data: T){ queue.append(data) } .. [Swift] 스택(Stack) 스택은 제한적으로 접근할 수 있는 나열 구조이다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 및 후입선출(LIFO - Last In First Out) 구조로 되어 있다. 스택 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 접시 더미와 마찬가지로 추가 또는 제거는 상단에서만 실용적이다. 스택의 구조 푸시 및 팝 작업을 사용한 스택 런타임의 간단한 표현. 스택(stack)은 제한적으ko.wikipedia.org 스택은 후입선출(LIFO - Last In First Out), 가장 최근에 넣은 것을 먼저 뽑고 예전에 넣은 걸 늦게 뽑고 싶을 때 사용한다.스택의 기능은 다음과 같다.push(data): 맨 앞에 데이터 넣기pop() : 맨 앞 데이터 뽑고 그 데이터 제거pe.. 이전 1 2 3 4 ··· 10 다음
