Test/Swift (4) 썸네일형 리스트형 [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.. [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 { .. 이전 1 다음
