분할 정복 알고리즘

분할 정복(Divide-and-Conquer) 알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다.

분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래 문제의 해를 얻는다.
분할된 입력에 대한 문제를 부분 문제(subproblem)라고 하고, 부분 문제의 해를 부분해라고 한다.
부분 문제는 더 이상 분할할 수 없을 때까지 계속 분할한다.
분할 횟수: log₂n

일반적으로 부분 문제들의 해를 취합하여 큰 부분 문제의 해를 구한다.

합병 정렬 (Merge Sort)

입력이 2개의 부분 문제로 분할, 부분문제의 크기가 ½로 감소하는 분할 정복 알고리즘이다.

- 합병 정렬 알고리즘

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]를 합병한다.
   }

- 예시

문제: 비내림차순으로 정렬된 크기가 u와 v인 배열 X와 Y를 합병하시오.
입력: 배열 크기 u,v, 비내림차순으로 정렬된 배열 X[1:u], Y[1:v] 
출력: 원소가 비내림차순으로 정렬된 합병된 배열 A[1:u+v] 
void Merge(index u, index v, keyType X[], keyType Y[], keyType A[]) { 
    index i, j, k; 
    i = 1; j = 1; k = 1; 
    while(i ≤ u && j ≤ v) { // X와 Y에 모두 원소가 남아 있을 때 까지 
        if (X[i] < Y[j]) { // X의 원소가 Y의 원소보다 크기가 작으면
            A[k] = X[i]; i++; // X의 원소를 A에 복사
        } else A[k] = Y[j]; 
        	j++; // 아니면 Y의 원소를 A에 복사
            k++;
        } if (i > u) // X의 원소가 끝났다면 Y의 나머지 원소들을 A에 복사 
			Copy Y[j:v] to A[k:u+v];
		else // Y의 원소가 끝났다면 X의 나머지 원소들을 A에 복사
			Copy X[i:u] to A[k:u+v]; 
		}

시간 복잡도

분할하는 부분은 배열의 중간 인덱스 계산과 2번의 재귀 호출이므로 O(1)이다.
합병의 수행 시간은 입력의 크기에 비례한다.
즉, 2개의 정렬된 배열 A와 B의 크기가 각각 n과 m이라면 최대 비교 횟수는 (n+m-1)이다.

각 층을 살펴보면 모든 숫자(n=8)가 합병에 참여했다.
합병은 입력 크기에 비례하므로 각 층에서 수행된 비교 횟수는 O(n)이다.

입력의 크기가 n이고 k번 ½로 분할하여 k개의 층이 생겼을 때, k=log₂n이다.
합병 정렬의 시간 복잡도: (층수) × O(n) = log₂n × O(n) = O(nlogn)

합병정렬의 단점

공간 복잡도가 O(n)이다.
- 입력을 위한 메모리 공간(입력 배열) 외에 추가로 입력과 같은 크기의 공간(임시 배열)이 별도로 필요하기 때문이다.
- 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문이다.

퀵 정렬 (Quick Sort)

분할 정복 알고리즘으로 분류되나, 사실 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘이다.
문제를 2개의 부분 문제로 분할하는데, 각 부분 문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘이다.

피봇(pivot)으로 정해진 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할한다. 피봇은 그 사이에 위치한다.
위와 동일한 과정을 재귀적으로 수행하여 정렬한다.

- 퀵 정렬 알고리즘

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) // 피봇보다 큰 그룹 }

QuickSort를 호출하면 피봇을 가장 왼쪽으로 이동시키고, 피봇보다 큰 수와 피봇보다 작은 수를 각각 교환한다.
교환이 끝나면 그 사이의 위치로 피봇을 옮긴다.

다음과 같은 과정을 반복한다.

- 예시

문제: 배열 A의 한 원소인 기준 원소(pivot element)를 중심으로 크기 순으로 분할 
입력: (1) 인덱스 low, high; (2) 인덱스 low에서 high까지의 A의 부분배열 
출력: 인덱스 low에서 high 사이의 A의 기준 원소의 위치를 나타내는 인덱스 pivot_point int Partition(index low, index high, index& pivot_point) { index i, j; keyType pivot_item; pivot_item = A[low]; // 기준 원소로 첫 번째 항목을 선택 
j=low; 
for(i = low + 1; i ≤ high; i++) {
    if (A[i]<pivot_item) { 
        j++;
        Interchange(A, i, j); 
    } 
    pivot_point = j;
    Interchange(A, low, pivot_point); // 기준 원소 값을 제 위치에 넣음 
}

시간 복잡도

퀵 정렬의 성능은 피봇 선택이 좌우한다.

최악 경우 시간 복잡도: O(n²)
피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되었을 때이다.

최선 경우 시간 복잡도: O(nlog₂n)
총 비교횟수 = O(n) × (층수) = O(n) × log₂n

평균 경우 시간 복잡도: O(nlog₂n)
피봇을 항상 랜덤하게 선택한다면, 최선 경우와 동일하다.

선택 문제 (Selection Problem)

n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다.
solution1: 최소 숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거한다. -> O(kn)
solution2: 숫자들을 정렬한 후, k번째 숫자를 찾는다. -> O(nlogn)
solution3: 이진탐색, 피봇을 이용한다.

- 선택 문제 알고리즘

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에서 찾기

선택 문제 알고리즘은 분할 정복 알고리즘이기도 하지만 랜덤(random) 알고리즘이기도 하다.
선택 알고리즘의 피봇을 랜덤하게 정하기 때문이다.
피봇이 입력 리스트를 너무 한 쪽으로 치우치게 분할하면 알고리즘의 수행 시간이 길어진다.

평균 경우 시간복잡도: O(n)

최근접 점의 쌍(Closest Pair) 찾기

2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제이다.
solution1: 모든 점에 대하여 각각의 두 점 사이의 거리를 계산한다. -> O(n²)
solution2: n개의 점을 ½로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 찾는다.
주의) 2개의 부분해를 취합할 때는 반드시 다음과 같은 경우를 고려해야 한다.

- 최근접 점의 상 분할 정복 알고리즘

ClosestPair(S) 
입력: x-좌표의 오름차순으로 정렬된 배열 S에는 i개의 점 (단, 각 점은 (x,y)로 표현된다.)
출력: S에 있는 점들 중 최근접 점의 쌍의 거리 
1. if (i ≤ 3) return (2 또는 3개의 점들 사이의 최근접 쌍) 
2. 정렬된 S를 같은 크기의 S⒧과 S⒭로 분할한다. |S|가 홀수이면, |S⒧| = |S⒭|+1이 되도록 분할한다. 
3. CP⒧ = ClosestPair(S⒧) // CP⒧은 S⒧에서의 최근접 점의 쌍 
4. CP⒭ = ClosestPair(S⒭) // CP⒭은 S⒭에서의 최근접 점의 쌍 
5. d = min{dist(CP⒧), dist(CP⒭)}일 때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾아서 이를 CP⒞라고 하자. 단, dist()는 두 점 사이의 거리이다. 
6. return (CP⒧, CP⒞, CP⒭ 중에서 거리가 가장 짧은 쌍)

시간 복잡도: O(nlog²n)