너비 우선 탐색 (Breadth First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐하는 방법 Example private class BFSExample { private lateinit var visited: BooleanArray private val resultList = mutableListOf() fun solution( nodeSize: Int, edgeSize: Int, edges: Array ) { val sortedEdges = edges.map { it.sorted() }.toTypedArray() // for (i in 1 until sortedEdges.size) { // println("node = $i, child = ${sortedEdges[i]}") // }..
kotlin
깊이 우선 탐색 (Depth First Search) 트리나 그래프에서 최대한 깊숙하게 탐색한 이후 가장 최근의 갈림길로 돌아가 다른 노드를 탐 DFS 구현 방법 재귀 호출을 이용한 구현 private fun dfs( edges: Array, node: Int = 1 ) { resultList.add(node) for (next in edges[node]) { if (!visited[next]) { visited[node] = true dfs(edges, next) visited[node] = false } } } 스택을 이용한 구현 private fun dfsUsingStack( edges: Array, node: Int = 1 ) { val deque = ArrayDeque() deque.add(no..
트리 순회 (Tree Traversal) 트리 구조의 모든 노드를 방문하는 방법 트리의 모든 노드를 한 번씩 방문하고 각 노드에 대해 원하는 작업을 수행하는 방법 전위 순회 (Preorder traversal) 현재 노드에 대한 작업을 수행 이후 각 자식 노드를 순서대로 방문하여 작업을 수행 Example fun preOrder(root: TreeNode) { print(root.data) root.left?.let { preOrder(it) } root.right?.let { preOrder(it) } } 중위 순회 (Inorder traversal) 현재 노드에 대한 작업을 수행 이후 각 자식 노드를 순서대로 방문하여 작업을 수행 Example fun inOrder(root: TreeNode) { r..
최단 경로 찾기 (Shortest path problem) 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 다익스트라 (Dijkstra) 알고리즘 주어진 출발점에서 시작 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 Pseudo code ShortestPath(G, s) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 출발점 s로부터 (n - 1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열 D를 ∞로 초기화시킨다. 단, D[s] = 0으로 초기화한다. // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다. 2. whi..
프림 최소 신장 트리 (Prim MST) 임의의 점 하나를 선택한 후, (n - 1)개의 선분을 하나씩 추가시켜 트리 Pseudo code PrimMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p] = 0으로 놓는다. // 배열 D[v]는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 요소 2. for (점 p가 아닌 각 점 v에 대하여) { // 배열 D의 초기화 3. if (선분 (p, v)가 그래프에 있으면) 4. D[v] = 선분 (p, v)의 가중치 5. else 6. D[v] = ∞ 7. } 8. T = {p} // 초기에 트리 T는..
크러스컬 최소 신장 트리 (Kruskal MST) 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 Pseudo code KruskalMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자. 2. T = ∅ // 트리 T를 초기화시킨다. 3. while ( T의 선분 수 < n-1 ) { 4. L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다. 5. if (선분 e가 T에 추가되어 사이클을 만들지 않으면) 6. e를 T에 추가시킨다. 7. else // e가 T에 추가되어 사이클이 만들어지는 경우 8. e..
동전 거스름돈 (Coin Change) 동전 거스름돈의 최소 동전 수를 찾는 문제 단, 동전 액면 500, 100, 50, 10, 1 Idea 남은 액수를 초과하지 않는 조건하에 가장 큰 액면의 동전을 택함 Pseudo code CoinChange(W) Input: 거스름돈 액수 W Output: 거스름돈 액수에 대한 최소 동전 수 1. change = W n500 = n100 = n50 = n10 = n1 = 0 // n500, n100, n50, n10, n1은 각각의 동전 카운트 2. while ( change ≥ 500 ) change = change-500, n500++ // 500원짜리 동전 수를 1 증가 3. while ( change ≥ 100 ) change = change-100, n1..
선택 문제 (Selection Problem) n 개의 숫자들 중 k 번째로 작은 숫자를 찾는 문제 간단한 idea 최소 숫자를 k번 찾는다 O(kn) 숫자들을 정렬한 후 k번째 숫자를 찾는다 O(nlogn) Idea 이진 탐색 (Binary Search) 정렬된 입력인 경우, 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 반으로 나눈 두 부분 중 한 부분만을 검색 선택 문제 입력이 정렬되지 않는 형태, 입력 숫자 중 피봇을 선택하여 분할 Pseudo code Selection(A, left, right, k) Input: A[left] ~ A[right]와 k, 단 1 ≤ k ≤ |A|, |A| = right - left + 1 Output: A[left] ~ A[right]에서 k 번째..
Quick Sort 문제를 2개의 부분 문제로 분할 각 부분 문제의 크기가 일정하지 않음 Idea 피봇 (pivot)을 임의로 설정하여 피봇보다 작은 숫자는 피봇 기준 왼쪽편으로, 피봇보다 큰 숫자는 피봇 기준 오른쪽으로 위치하도록 분할하고 피봇을 그 사이에 놓는다. 분할된 부분 문제들에서도 재귀적으로 수행 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘 Pseudo code QuickSort(A, left, right) Input: Array A[left] ~ A[right] Output: Sorted Array A[left] ~ A[right] if (left < right) { p := partition(A, left, right) QuickSort(A, left, p) //..
합병정렬 (Merge Sort) 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘 합병 (Merge) 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자로 합치는 것 Example Array A: 6, 14, 18, 20, 29 Array B: 1, 2, 15, 25, 30, 45 Array C: 1, 2, 6, 14, 15, 18, 20, 25, 29, 30, 45 Pseudo code MergeSort(A, start, end) Input: A[start] ~ A[end] Output: Sorted A[start] ~ A[end] if (start < end) { // 배열의 원소의 수가 2개 이상이면 k = (start + end) / 2 // k는 반으로 나누기 위한 중간 원소의..
