분할 정복 알고리즘

분할 정복 알고리즘 (Divide and Conquer) 이란 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래 문제의 해를 얻는다. 여기서 분할된 입력에 대한 문제를 부분문제라고 하고, 부분문제의 해를 부분해라고 한다. 부분문제는 더 이상 분할할 수 없을 때까지 계속 분할한다. 

 

3.2 퀵정렬

1. 임의의 pivot 을 선정하고 가장 왼쪽의 값과 교환한다. 

 

2. low 인덱스를 오른쪽으로 한 칸씩 이동시키다가 pivot 인 9보다 큰 값이 나오면 정지한다. 이후에는 high 인덱스를 왼쪽으로 한 칸씩 이동시키다가 반대로 Pivot 인 9보다 작은 값이 나오면 정지한다. 그리고선 low 인덱스와 high 인덱스가 가리키는 값을 교환한다. 

 

3. 같은 방식으로 진행한다. 

4. 그러다보면 high 와 low 가 서로를 지나쳐 가는 상황이 온다. 그 때는 left 값과 high 값을 교환하여 pivot 의 자리를 확정한다. 

 

5. 이제 pivot 기준 왼쪽을 다시 정렬한다. 이들 중에서 임의의 pivot 을 또 선정한다. 

 

6. low, high 인덱스를 이동하는 과정을 반복하다 low 와 high 가 교차하는 순간에 left 와 high 값을 교환하는 같은 방식으로 진행한다. 

pivot 을 임의로 선택하다보니, 정렬 전과 후의 결과가 동일하게 나올 수도 있다. 그래도 pivot 인 6의 자리를 확정지을 수 있다는 것에 의의를 둔다. 

7. 확정된 Pivot 인 6을 기준으로 [4,3,5] 를 동일한 방법으로 정렬한다. 9의 오른쪽도 마찬가지!

 

3.3 선택정렬

Selection(배열, left 인덱스, right 인덱스, k 번째 작은 원소)

 

7번째 작은 숫자를 찾아야 한다고 해보자. 

1. 우선 퀵정렬을 한 번 진행한다. Selection (A,0,11,7)

 

2. Pivot 이전에는 값이 4개, pivot 까지 포함하면 5개 이므로 7번째 값은 Pivot 의 오른쪽에 있을 것이다. 따라서 오른쪽 부분만 정렬하여 7-5=2 번째로 작은 수를 찾으면 된다. Selection (A,5,11,2) 

 

3. 2번째로 작은 수를 찾기 위해서는 Pivot (14) 의 왼쪽을 보면 된다. Selection(A,5,8,2)

 

두 번째로 작은 수를 발견하게 된다. A[6]=10

3.4 최근접 쌍 찾기

1. n개의 점을 1/2 로 분할한다 (0~4 와 5~9). 왼쪽 부분의 최근접 쌍의 거리는 10, 오른쪽 부분의 최근접 쌍의 거리는 15로 가정한다. 

x좌표 오름차순 정렬, y좌표 생략

 

2. 왼쪽과 오른쪽의 최근접 쌍의 거리 중 더 작은 수를 선택한다 (10). 왼쪽 부분의 가장 오른쪽 점인 4번 기준으로 10 만큼 거리의 점들을 중간영역으로 포함시킨다. 오른쪽도 동일하게 진행한다. 

 

3. 중간영역에서 최근접 쌍을 찾는다. 이 문제에서는 7로 가정하자. 

4. $CP_L$ (left 의 closest point), $CP_R$ (right의 closest point), $CP_C$ (center의 closest point) 중에서 거리가 가장 짧은 쌍을 리턴한다.