Software

최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 (b)는 최소 신장 트리 (c)는 가중치의 합이 (b)보다 큼 (d)는 트리가 주어진 그래프의 모든 노드를 포함하지 않음 Idea 사이클이 없도록 모든 점을 연결 그래프의 점의 수가 n인 경우 신장 트리에 (n - 1)개의 선분이 존재 트리에 선분을 하나 추가할 경우, 반드시 사이클이 형성 관련 알고리즘 크러스컬 (Kruskal) 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 2024.03.10 - [Algorithm] - [알고리즘] 크러스컬 최소 신장 트리 (Kruskal MST) 프림 (Prim) 알..

동전 거스름돈 (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..

최근접 점의 쌍 찾기 (Closest Pair of Points Problem) 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 간단한 idea 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는다 example 1, 2, 3, 4, 5 총 5개의 점이 주어진 경우 비교해야 할 쌍의 개수 = nC2 = n(n-1)/2 시간 복잡도는 O(n^2) O(n^2)보다 효율적인 분할 정복 이용 n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 찾는다 2개의 부분해를 취합할 때 아래와 같이 양쪽을 비교해서 짧은 해라고 답으로 정할 수 없다. 거리가 짧은 해 이내..

선택 문제 (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는 반으로 나누기 위한 중간 원소의..