![[[NOTE 3] 분할 정복 알고리즘.pdf]] | 일자 | 계획 | 진행상황 | | ---- | ----------------- | ---- | | 3/25 | 분할 정복 알고리즘, 합병 정렬 | 💻 | | 3/26 | 퀵 정렬 | 💻 | | 3/26 | 선택 문제 | 💻 | | 3/27 | 최근접 점의 쌍 찾기 | 💻 | | 3/27 | 문서 최종 업데이트 | 💻 | # 0. 분할 정복 알고리즘 ## 0.1 개념 - 주어진 문제의 입력을 **분할**하여 문제를 해결(**정복**)하는 방식의 알고리즘 - 입력 분할 - 분할한 입력에 대해 *동일한 알고리즘을 적용*해 해를 계산 - *해를 취합*해 원래 문제의 해를 얻음 - 부분 문제와 부분 해 - `부분 문제` 분할된 입력에 대한 문제 - 더 이상 분할할 수 없을 때까지 분할 - `부분 해` 부분 문제의 해 ## 0.2 분할 과정 크기가 n인 입력을 3개로 분할, 각각 분할된 부분 문제의 크기가 n/2일 경우의 분할 예 ```mermaid flowchart TB subgraph L0["Level 0"] A["문제 1개<br/>크기 n"] end subgraph L1["Level 1"] B1["문제 1<br/>크기 n/2"] B2["문제 2<br/>크기 n/2"] B3["문제 3<br/>크기 n/2"] end subgraph L2["Level 2"] C1["크기 n/2²"] C2["크기 n/2²"] C3["크기 n/2²"] C4["크기 n/2²"] C5["크기 n/2²"] C6["크기 n/2²"] C7["크기 n/2²"] C8["크기 n/2²"] C9["크기 n/2²"] end A --> B1 A --> B2 A --> B3 B1 --> C1 B1 --> C2 B1 --> C3 B2 --> C4 B2 --> C5 B2 --> C6 B3 --> C7 B3 --> C8 B3 --> C9 ``` - **3개로 나눈다** = 한 문제에서 **재귀 호출이 3번** 나온다는 뜻 - **각 크기가 n/2다** = 각 재귀 호출이 받는 **입력 크기**가 원래의 절반이라는 뜻 - **하위 문제 개수**와 **하위 문제 크기**는 꼭 같은 기준으로 움직이지 않음. ## 0.3 입력 크기가 n일 때 총 분할 횟수 - 총 분할한 횟수 or 트리 높이 $k = log_2 n$ - $n/2^k = 1$일 때 분할 못 함, 즉 리프(종료 조건). ## 0.4 정복 과정 - 대부분의 분할 정복 알고리즘의 특징: 단순히 분할만 해서는 해를 구할 수 X - 따라서 부분 문제들을 '정복'해야 함 - 부분 해를 찾고 - 정복(취합)함 - 문제에 따라 방법이 다름 ## 0.5 분할 정복 알고리즘의 분류 - `분류 기준` - 부분 문제의 수 - 부분 문제의 크기 - `분류` - 문제가 $a$개로 분할되고, 부분 문제의 크기가 $1/b$로 감소 - $a = b = 2$ 인 경우 [[#1. 합병 정렬 (Merge Sort)]], `최근접 점의 쌍 찾기`, `공제선 문제` - $a=3, b=2$인 경우 `큰 정수의 곱셈 - 카라츠바 알고리즘` - $a=4, b=2$인 경우 `큰 정수의 곱셈 - 기본 곱셈` - $a=7, b=2$인 경우 `Strassen의 행렬 곱셈 알고리즘` - 문제가 $2$개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소 - `퀵 정렬` - 문제가 $2$개로 분할되나, 그 중 $1$개는 고려 X, 부분 문제의 크기가 $1/2$로 감소 - `이진 탐색` - 문제가 $2$개로 분할되나, 그 중 $1$개는 고려 X, 부분 문제의 크기가 일정하지 않은 크기로 감소 - `선택 문제 알고리즘` - 부분 문제의 크기가 $1, 2$개씩 감소 - `삽입 정렬` - `피보나치 수의 계산` --- # 1. 합병 정렬 (Merge Sort) ## 1.1 정의 입력이 $2$개의 부분 문제로 분할 + 부분 문제의 크기가 $1/2$로 감소 - $n$개의 숫자들을 $n/2$개씩 $2$개의 부분 문제로 분할 - 각각의 부분 문제를 **순환**으로 합병 정렬 - $2$개의 정렬된 부분을 합병하여 정렬(정복) → 합병 과정이 문제를 정복하는 것 ## 1.2 합병 (merge) - 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자로 합치는 것 - `예시` - 배열 A: 6 14 - 배열 B: 1 2 - 배열 C (merged): 1 2 6 14 ## 1.3 알고리즘 ### 1.3.1 의사 코드 ``` MergeSort(A, p, q) 입력: A[p] ~ A[q] 출력: 정렬된 A[p] ~ A[q] 1. if (p < q) { // 배열의 원소의 수가 2개 이상이면 2. k = ⌊(p + q) / 2⌋ // k는 중간 원소의 인덱스 3. MergeSort(A, p, k) // 앞부분 순환 호출 4. MergeSort(A, k+1, q) // 뒷부분 순환 호출 5. A[p]~A[k]와 A[k+1]~A[q]를 합병 } ``` ### 1.3.2 머메이드 예시 ```mermaid flowchart TB A["[37, 10, 22, 30, 35, 13, 25, 24]"] A --> B1["[37, 10, 22, 30]"] A --> B2["[35, 13, 25, 24]"] %% Left side B1 --> C1["[37, 10]"] B1 --> C2["[22, 30]"] C1 --> D1["[37]"] C1 --> D2["[10]"] C2 --> D3["[22]"] C2 --> D4["[30]"] D1 --> E1["[10, 37]"] D2 --> E1 D3 --> E2["[22, 30]"] D4 --> E2 E1 --> F1["[10, 22, 30, 37]"] E2 --> F1 %% Right side B2 --> C3["[35, 13]"] B2 --> C4["[25, 24]"] C3 --> D5["[35]"] C3 --> D6["[13]"] C4 --> D7["[25]"] C4 --> D8["[24]"] D5 --> E3["[13, 35]"] D6 --> E3 D7 --> E4["[24, 25]"] D8 --> E4 E3 --> F2["[13, 24, 25, 35]"] E4 --> F2 %% Final merge F1 --> G["[10, 13, 22, 24, 25, 30, 35, 37]"] F2 --> G ``` ## 1.4 시간 복잡도 $O(nlog_2n)$ - `분할` 배열의 중간 인덱스 계산과 2회의 순환 호출이므로 $O(1)$시간 소요 - `합병` 수행 시간이 입력 크기에 비례. - 2개의 정렬된 배열 A와 B의 크기가 각각 $m$과 $n$이라면 - 최대 비교 횟수 $= (m+n-1)$ - 합병의 시간 복잡도 $= O(m+n)$ - `총` 각각 합병에 대해 몇 번의 비교가 수행되었는지를 계산해 이들을 모두 합하면 됨 - `층별 비교 횟수` - 각 층을 보면, 모든 숫자가 합병에 참여 - 합병은 입력 크기에 비례 → 각 층에서 수행된 비교 횟수는 $O(n)$ - `층수의 계산` - 아까 나왔던 대로 $k = log_2 n$ - `입력 크기 n 기준` - $(층수) \times O(n) = log_2 n \times O(n) = O(nlog_2 n)$ ## 1.5 합병 정렬의 단점 - 대부분의 정렬 알고리즘은 아래만 사용 - 입력을 위한 메모리 공간 - $O(1)$ 크기의 메모리 공간 (입력 크기 $n$과 상관없는 크기의 공간. 변수, 인덱스 등) - 합병 정렬의 공간 복잡도: $O(n)$ - 입력 공간 외에 임시 배열이 별도로 필요. (합병한 거 저장해야 하니...) ## 1.6 응용 - 합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘 - 연결 리스트 내부 데이터 정렬 시에도 퀵/힙 정렬보다 효율적 - Multi-Core CPU + GPU 등장으로 정렬 알고리즘을 병렬화하는 데 활용 ## 1.7 F# 구현 연습 [연관 이슈](https://github.com/gyesswhat/2026-algorithm-study/issues/1) --- # 2. 퀵 정렬 (Quick Sort) ## 2.1 정의 - `분류` 분할 정복 알고리즘 - `but` 정복 후 분할하는 알고리즘 - `분할` 문제를 2개의 부분 문제로 분할 - 각 부분 문제의 크기가 일정 X - `아이디어` pivot(특정한 원소)을 기준으로 작은 숫자는 왼편, 큰 숫자는 오른편에 위치하도록 분할 후 pivot을 그 사이에 둠 - 분할된 부분문제들에 대해서도 동일한 과정을 **순환으로** 수행 ## 2.2 피봇 - 분할된 왼편이나 오른편 부분에 포함되지 않음 ## 2.3 알고리즘 ``` QuickSort(A, left, right) 입력: 배열 A[left]~A[right] 출력: 정렬된 배열 A[left]~A[right] 1. if (left < right) { 2. 피봇을 A[left]~A[right]에서 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자들은 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다. 3. QuickSort(A, left, p-1) // 피봇보다 작은 그룹 4. QuickSort(A, p+1, right) // 피봇보다 큰 그룹 } ``` ## 2.4 시간 복잡도 - `성능` 피봇 선택이 좌우함. - `최악` 항상 가장 작은 숫자가 선택되는 경우 $O(n^2)$ - `최선` 균등하게 분할되는 피봇 선택 $O(n\log n)$ - 각 층에서는 각각의 원소가 각 부분의 피봇과 $1$회씩 비교, 즉 비교 횟수 $O(n)$ - 총 비교 횟수 $= O(n) \times (층수) = O(n) \times (\log n)$ - $k = \log n$ - `평균` 피봇을 항상 랜덤하게 선택한다고 하면, 평균 경우를 구할 수 있음. 최선과 동일한 $O(n\log n)$ ## 2.5 피봇 선정 방법 1. 랜덤 선정 2. 3 숫자의 중앙값으로 선정하는 방법 (Median-of-Three) 1. 가장 왼쪽, 중간, 오른쪽 숫자 중에서 중앙값으로 피봇을 정함 2. `예시` [31, 1, 26] 중에서는 26을 피봇으로 사용 3. Median-of-Medians (Tukey's Ninther) 1. 3등분한 후 각 부분에서 가장 왼쪽/중간/오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 피봇으로 정함 ## 2.6 성능 향상 방법 - `문제` 입력의 크기가 매우 클 때: 삽입 정렬을 동시 사용 - 입력의 크기가 작을 때에는, 퀵 정렬이 삽입 정렬보다 빠르지만은 X - `why?` 순환 호출 - 부분 문제의 크기가 작아지면 분할(순환 호출)을 중단하고 삽입 정렬을 사용 ## 2.7 응용 - 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘 - 실질적으로 어느 정렬 알고리즘보다 좋은 성능 ## 2.8 FSharp 구현 1. 우선 피봇 선택 메소드 3개를 구현하고 2. 이거 테스트한 다음에 3. 괜찮으면 퀵정렬 메소드로 넘어갈 것 아이디어 노트 1. 배열 2개일 경우에는 median of three도, Tukey's Ninther도 못 쓰기 때문에 이런 경우도 반영해야 함 findMedian에서 1. 메소드의 책임 범위를 명확히 설정해보자 1. findMedian에서 그냥 Option말고 int 반환하도록 하고 2. 오류가 생길 케이스는 상위에서 막기 2. 생각해보니 일단 삽입정렬을 구현해야 할 수 있음.. 그거나 하자... 1. insertionSort를 rec으로? // 1. insertionSort에 4;2;3;1 들어옴 // 2. head 4랑 2;3;1로 insert 호출 // 3. 그럼 어쩄든 첫 try에서는 2;3;1;4가 나와야 함 // 4. recursive면 안에 recursive를 멈출 조건이 있어야 함 // 이 조건을 어떻게 설정할 것인가... // 사실 리스트가 줄어드는;; 형태가 아니면 어떻게 설정할 방법이 없음 근데 그걸 어케 줄이는데? // 왜 rec이어야 하는가? // 함수의 역할... insert는 insert만 수행해야 함 // insert부터! // insertSort에 들어옴 // head::rest면 rest로 insertSort // rest 정렬되고 나면, insert로 head -> 넣은 전체 리스트 반환 // [4;2;3;1] 들어옴 // [2;3;1] insertSort // [3;1] insertSort // [1] insertSort -> [1] // insert 3 [1] // [1;3] // insert 2 [1;3] // ... 둘 다 rec이어야 함. findMedianIndex도 rec으로 해도 되지 않나? ## 2.9 BenchmarkDotNet으로 피봇 선택 알고리즘 비교하기 - [[2.1.1 분할 정복 알고리즘 - 퀵 정렬 관련 - 피봇 선택 방식 Benchmark]] 참고. --- # 3. 선택 문제 (Selection Problem) ## 3.1 정의 "$n$개의 숫자들 중에서 $k$번째로 작은 숫자를 찾는 문제" - `단순한 알고리즘` - 최소 숫자를 $k$번 찾는다 (최악의 경우: $O(kn)$) - 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거한다 - 숫자들을 정렬한 후, $k$번째 숫자를 찾는다 (최악의 경우: $O(n \log n)$) - `아이디어` - 이진 탐색 - 정렬된 입력의 중간 숫자와 찾고자 하는 숫자를 비교함으로써, - 입력을 $1/2$로 나눈 두 부분 중에서 한 부분만을 검색 - 선택 문제 - 입력은 정렬 X, 입력 숫자들 중에서 [[#2. 퀵 정렬 (Quick Sort)]] 처럼 피봇 선택해서 분할 - small group은 피봇보다 작은 숫자의 그룹, large group은 피봇보타 큰 숫자의 그룹 - 이렇게 분할했을 때 알아야 할 것은 각 그룹의 크기, 즉, 숫자의 개수 - `왜?` 크기를 알면 -> k번째 작은 숫자가 어디 그룹에 있는지 알 수 있고 -> 그 다음에는 그 그룹에서 몇 번째로 작은 숫자를 찾아야 하는지를 알 수 있다 - small group에 $k$번째 작은 숫자가 속한 경우 - $k$번째 작은 숫자를 small group에서 찾는다 - large group에 $k$번째 작은 숫자가 있는 경우 - $(k - |Small\ group| - 1)$번째로 작은 숫자를 large group에서 찾아야 한다 - $|Small\ group|$은 Small group에 있는 숫자의 개수이고, $1$은 피봇에 해당한다 ## 3.2 알고리즘 ```pseudo Selection(A, left, right, k) 입력: A[left]~A[right]와 k, 단, 1 ≤ k ≤ |A|, |A| = right - left + 1 출력: A[left]~A[right]에서 k 번째 작은 원소 1. 피봇을 A[left]~A[right]에서 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후, 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자는 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다. 2. S = (p-1) - left + 1 // S = Small group의 크기 3. if (k ≤ S) Selection(A, left, p-1, k) // Small group에서 찾기 4. else if (k = S + 1) return A[p] // 피봇 = k번째 작은 숫자 5. else Selection(A, p+1, right, k - S - 1) // Large group에서 찾기 ``` ## 3.3 Selection 알고리즘 고려 사항: 피봇 선택 1. 분할 정복이기도 하지만, 랜덤 알고리즘이기도 하다 2. 피봇이 입력을 너무 한쪽으로 치우치게 분할하면 1. 즉, $|Small\ group| << |Large\ group|$또는 $|Small\ group| >> |Large\ group|$일 때에는 알고리즘의 수행 시간이 길어진다 3. 선택 알고리즘이 호출될 때마다 line 1에서 입력을 한쪽으로 치우치게 분할될 확률은? = 동전을 던질 때 한쪽 면이 나오는 확률 ### 3.3.1 good/bad 분할 정의 - 분할된 두 그룹 중의 하나의 크기가 입력 크기의 $3/4$과 같거나 그보다 크게 분할하면 나쁜(bad) 분할, 그 반대의 경우 좋은(good) 분할 (각 확률 1/2) - 입력 크기가 $n$에서부터 $3/4$배로 연속적으로 감소되고, 크기가 $1$일 때에는 더이상 분할할 수 없다. - $n + \frac 3 4 n + (\frac 3 4)^2 n + (\frac 3 4)^3 n + \cdots + (\frac 3 4)^{i-1} n + (\frac 3 4)^i n$ - $n \left[1 + \frac 3 4 + (\frac 3 4)^2 + (\frac 3 4)^3 + \cdots + (\frac 3 4)^{i-1} + (\frac 3 4)^i \right] \le 2n = O(n)$ - 평균 2회에 good 분할이 되므로 $2 \times O(n) = O(n)$ ### 3.3.2 시간 복잡도 1. 피봇을 랜덤하게 정했을 때 good 분할이 될 확률이 $1/2$이므로 평균 $2$회 연속해서 랜덤하게 피봇을 정하면 good 분할을 할 수 있음. 2. 매 $2$회 호출마다 good 분할이 되므로, good 분할만 연속하여 이루어졌을 때만의 시간 복잡도를 구하여, 그 값에 $2$를 곱하면 평균 경우 시간 복잡도를 얻을 수 있다 ## 3.4 선택 알고리즘과 이진 탐색 1. 유사성 1. 이진 탐색은 분할과정을 진행하면서 범위를 $1/2$씩 좁혀가며 찾고자 하는 숫자를 탐색 2. 선택 알고리즘은 피봇으로 분할하여 범위를 좁혀감 2. 공통점: 부분 문제들을 취합하는 과정이 별도로 필요 없다 ## 3.5 FSharp 구현 ```pseudo Selection(A, left, right, k) 입력: A[left]~A[right]와 k, 단, 1 ≤ k ≤ |A|, |A| = right - left + 1 출력: A[left]~A[right]에서 k 번째 작은 원소 1. 피봇을 A[left]~A[right]에서 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후, 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자는 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다. 2. S = (p-1) - left + 1 // S = Small group의 크기 3. if (k ≤ S) Selection(A, left, p-1, k) // Small group에서 찾기 4. else if (k = S + 1) return A[p] // 피봇 = k번째 작은 숫자 5. else Selection(A, p+1, right, k - S - 1) // Large group에서 찾기 ``` 1차 구현: 무한루프;; 무엇이 문제인가? 재귀로 했으면 빠져나올 방법이 있어야 하는데 없... 나? 인덱스로 비교하고 있네... 이래서 안 됐던 거군... --- # 4. 최근접 점의 쌍 찾기 (Closest Pair) ## 4.1 정의 - 2차원 평면상의 $n$개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 - 간단한 방법 - 모든 점에 대하여 각각의 두 점 사이의 거리를 계산해 가장 가까운 점의 쌍을 찾음 - 이렇게 되면, 시간 복잡도가 $O(n^2)$ - 비교해야 하는 쌍 $_n C _2 = n(n-1)/2$ - $n=5$면, $5(5-4)/2 = 10$ - $n(n-1)/2 = O(n^2)$ - 한 쌍의 거리 계산은 $O(1)$ - 시간 복잡도는 $O(n^2) \times O(1) = O(n^2)$ - 더 효율적인 방법이 없을까? = 분할 정복 ## 4.2 알고리즘 ### 4.2.1 아이디어 - $n$개의 점을 $1/2$로 분할해 각각의 부분 문제에서 최근접 점의 쌍을 찾고, $2$개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾음 - `note` - 취합할 때는 중간 영역을 고려해야 함 - (ppt 52p) $10$과 $15$ 중에서 짧은 거리인 $10$ 이내의 중간 영역 안에 있는 점들 중에 더 근접한 점의 쌍이 있는지 확인 - 중간 영역에 있는 점들을 찾는 방법 - `d = min{왼쪽 부분의 최근접 점의 쌍 사이의 거리, 오른쪽 부분의 최근접 점의 쌍 사이의 거리}` - 배열에는 점들이 x-좌표의 오름차순으로 정렬되어 있고, 각 점의 y-좌표는 생략 - `중간 영역에 속한 점 = {왼쪽 부분 문제의 가장 오른쪽 점(왼쪽 중간점)의 x-좌표에서 d를 뺀 값과 오른쪽 부분 문제의 가장 왼쪽 점(오른쪽 중간점)의 x-좌표에 d를 더한 값 사이의 x-좌표 값을 가진 점들}` - (ppt 53p) d=10이면, 점 (25, -), (26, -), (28, -), (30, -), (37, -)이 중간 영역에 속함 ### 4.2.2. 의사 코드 ```pseudo ClosestPair(S) 입력: x-좌표의 오름차순으로 정렬된 배열 S에 있는 i개의 점. 단, 각 점은 (x, y)로 표현 출력: S에 있는 점들 중 최근접 점의 쌍의 거리 1. if (i ≤ 3) return (2 또는 3개의 점들 사이의 최근접 쌍) 2. 정렬된 S를 같은 크기의 S_L 과 S_R 로 분할한다. |S|가 홀수이면, |S_L| = |S_R| + 1이 되도록 분할 3. CP_L = ClosestPair(S_L) // CP_L은 S_L에서의 최근접 점의 쌍 4. CP_R = ClosestPair(S_R) // CP_R은 S_R에서의 최근접 점의 쌍 5. d = min{ dist(CP_L), dist(CP_R) }일 때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾아서 이를 CP_C 라고 하자. 단, dist()는 두 점 사이의 거리 6. return (CP_L, CP_C, CP_R 중에서 거리가 가장 짧은 쌍) ``` 1. ClosestPair(S)로 호출 (ppt 56p~) 1. `Line 1` S의 점의 수 > 3이므로 다음 line을 수행 2. `Line 2` S를 S_L과 S_R로 분할 2. ClosestPair(S_L) 호출 3. ClosestPair(S_R) 호출 4. `Line 5` 중간 영역에서 CP_C 찾음 5. `Line 6` dist(CP_L)=10, dist(CP_C)=5, dist(CP_R)=15 중에서 가장 거리가 짧은 쌍인 CP_C를 최근접 쌍의 점으로 최종적으로 리턴 ## 4.3 시간 복잡도: $O(n \log^2 n)$ - $S$에 $n$개의 점이 있다면 preprocessing 과정으로서 $S$의 점을 x-좌표로 정렬: $O(n \log n)$ - `Line 1` $S$에 3개의 점이 있는 경우에 3번의 거리 계산 필요, $S$의 점의 수가 2이면 1번의 거리 계산이 필요하므로 $O(1)$ 시간이 걸림 - `Line 2` 정렬된 $S$를 $S_L$과 $S_R$로 분할하는데, 이미 배열에 정렬되어 있으므로, 배열의 중간 인덱스로 분할하면 됨. 이는 $O(1)$시간이 걸림. - `Line 3-4` $S_L$과 $S_R$에 대해 각각 ClosestPair를 호출하는데, 분할하며 호출되는 과정은 합병 정렬과 동일. - `Line 5` d=min{dist($CP_L$), dist($CP_R$)}일 때 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾음. - 이를 위해 먼저 중간 영역에 있는 점들을 y-좌표 기준으로 정렬 $O(n \log n)$ - 아래에서 위로 각 점을 기준으로 거리가 d 이내인 주변 점들 사이 거리 계산. 계산해야 하는 주변 점들의 수는 $O(1)$ - 이 중에서 최근접 점의 쌍 찾음 - `Line 6` $3$개의 점의 쌍 중에 가장 짧은 거리를 가진 점의 쌍을 리턴하므로 $O(1)$시간 - CP 알고리즘의 분할과정은 합병 정렬의 분할과정과 동일. `but` Line 5-6 - 해 취합해 올라가는 과정 - 에서 $O(n \log n)$시간 필요 - $k$층까지 분할된 후, 층별로 위 취합 과정 필요 - 각 층의 수행 시간 $O(n \log n)$ - 여기에 층 수인 $\log n$을 곱하면 $O(n \log^2 n)$ ## 4.4 FSharp 알고리즘 구현 d = min{왼쪽 부분의 최근접 점의 쌍 사이의 거리, 오른쪽 부분의 최근접 점의 쌍 사이의 거리} {왼쪽 부분 문제의 가장 오른쪽 점 (왼쪽 중간점)의 x-좌표에서 d를 뺀 값 과 오른쪽 부분 문제의 가장 왼쪽 점 (오른쪽 중간점)의 x-좌표에 d를 더한 값 사이의 x-좌표 값을 가진 점들} -> 이거 음... 음............ findMiddlePoints의 입력으로 멀 줘야할까?.... d랑 leftGroup이랑 rightGroup? d는 변수명 minOuterDistance로... 음... 그당므에.. ㅇ므.ㅁㄴ,ㅇ,.ㅁ # 5. 분할 정복 적용에 있어 주의할 점 - `부분 문제의 입력 크기가 커지는 경우` 입력이 분할될 때마다 부분 문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 커지는 경우 - `예시` $n$번째의 피보나치 수를 구하기 - $F(n) = F(n-1) + F(n-2)$라서 적절해 보이지만, 사실상 $n$의 값 자체가 입력 크기. $2$개의 부분 문제인 $F(n-1)$과 $F(n-2)$의 입력 크기는 $(n-1) + (n-2) = (2n-3)$이 되어서, 분할 후 입력 크기가 거의 $2$배로 증가. - `취합(정복) 과정` 취합(정복) 과정을 주의해야 함. 분할만 해서 효율적 알고리즘이 되는 건 X. - 기하 관련 문제들이 주로 효율적 분할 정복 알고리즘으로 해결되는데, 이건 기하 문제 특성상 취합 과정이 문제 해결에 잘 부합되기 때문!