걸어가는 개발자

Merge Sort(병합 정렬) 두부분으로 쪼개는 작업을재귀적으로 반복한뒤 분리한 순서와 반대로 크기가 작은 값부터 병합해 나가는 분할정복 알고리즘 시간복잡도 O(nlogn) Merge Sort(병합 정렬) 순서 리스트를 반으로 나눈다(Divide) 왼쪽 리스트와 오른쪽 리스트를 각각 정렬(Conquer) 정렬된 두 리스트를 하나의 정렬된 리스트로 합병(Combine) func mergeSort(_ list: [Int]) -> [Int] { if list.count

Dijkstra(다익스트라) Dynamic Programming을 이용한 최단경로 알고리즘 특정 노드에서 다른 나머지 노드로 가는 최단경로를 구할 때 사용 첫노드부터 모든 노드의 최단거리 저장하는 배열 및 우선순위큐 사용 Dijkstra 알고리즘 순서 1. 노드의 개수만큼 distances 생성, 시작 노드의 값은 0 2. 우선순위 큐 생성 및 첫노드 가중치 0 3. 우선순위큐에서 추출된 노드와 연결된 인접 노드와의 거리 + 추출된 노드 가중치를 계산하여 distances의 값보다 적으면 distances업데이트 및 우선순위큐 insert 구현 코드 struct NodePriority: Comparable { var node: String = "" var priority: Int = 0 static fu..

Floyd Warshall 그래프에서 도착할 수 있는 모든 쌍에대한 최단거리를 구하는 알고리즘 그래프를 기준으로 이차원배열 생성 Dynamic Programing기법을 이용해 각 쌍의 최단거리를 계산 및 업데이트 예제) 그래프 최소 왕복 길이 계산 초기 cost INF 1 5 INF INF 2 INF 1 INF 플로이드 와샬 알고리즘 후 cost INF 1 3 INF 3 2 INF 1 3 func floydWarshall(inputs: [[Int]], node: Int) -> Int { let INF = 987654321 var result = INF var cost = Array(repeating: Array(repeating: INF, count: node), count: node) for input..

Binary Search(이분탐색) 데이터의 중간값을 확인하면서 탐색하는 기법 데이터가 정렬 되있을 때 효과적 시간 복잡도는 O(logN) func binarySearch(list: [Int], element: Int) -> Int? { var firstIndex = 0 var lastIndex = list.count - 1 while firstIndex element { lastIndex = midIndex - 1 } else { return midIndex } } return nil } binarySearch(list: [1, 3, 4, 5, 6, 7, 9], element: 7) // Optional(5) binarySearch(list: [1, 3, 4, 5, 6, 7, 9], element: 8..

Combination 하나의 리스트에서 중복되지 않는 값들을 n개의 조합으로 구함 func combination(_ target: [T], _ count: Int) -> [[T]] { var result = [[T]]() func combi(_ nowTarget: [T], _ index: Int) { if nowTarget.count == count { result.append(nowTarget) return } for i in index.. [[T]] { var result: [[T]] = [] var visited = Array(repeating: false, count: target.count) func permutate(_ nowTarget: [T]) { if nowTarget.count == c..