분할정복법 Divide and Conquer

🍰 분할 정복법

• 문제의 사례를 2개 이상의 더 작은 사례로 나누어 divide 각 작은 사례에 대한 해답 conquer을 쉽게 얻을 수 있으면 이들의 해답을 결합 combine하여 원 문제의 해답을 얻는 방식

• 문제를 나누는 과정: 해답을 쉽게 얻을 수 있을 때까지 반복적으로 적용
• 작은 사례는 보통 원 문제와 같지만 작은 규모
• 하향식 접근 방법 (분할 → 정복 → 통합)
• 보통 재귀 프로시저로 먼저 해결한 다음, 보다 효율적인 반복 프로시저 (for, while 등)가 없는지 검토

---

🍰 이진 검색

• 배열로 구현된 정렬된 리스트에 대한 검색

• 찾고자 하는 x가 중간 항에 있으면 종료, 아니면
• 분할: 배열을 중간을 기준으로 이등분하여 2개의 부분 배열 생성 후 x와 중간 항 비교
• 정복: 선택한 부분 배열에서 x 찾기. 부분 배열의 크기가 너무 작지 않은 이상 재귀 방법으로 찾음
• 통합: 원 해답을 부분 배열에 대한 해답으로부터 얻음

알고리즘

• 문제: n개의 키로 구성된 정렬된 배열 S에 키 x가 있는가?
• 입력: 양의 정수 n, 오름차순으로 정렬된 배열 S, 키 x
• 출력: 키 x가 배열에 있으면 그것의 index, 없으면 -1

코드

int BinSearch(index low, index high) {
    if(low > high) return -1;        
      // low = high -> data 1개여도 비교 1번은 함
    else {
        index mid = ⌊(low + high) / 2⌋;
        if(x == S[mid]) return mid;
        else if(x < S[mid]) BinSearch(low, mid-1);
        else BinSearch(mid+1, high);                 // 비교 연산 1번
    }
}

기본 연산: 비교

T(0) = 0, T(1) = 1
T(n) = T(n/2) + 1     (재현식)
    T: 함수 호출 횟수, 비교 연산 횟수

• 입력인 n, x, S가 파라미터로 사용되지 않음
  • 이들은 재귀 호출되면서 변경되지 않기 때문에
  • 재귀 호출할 때마다 이러한 변하지 않는 파라미터를 갖고 다니는 것은 매우 낭비
  • low, high 사용

---

최악의 경우

• 최악의 경우: 기본 연산이 가장 많이 수행되는 경우

• 함수 호출마다 x와 S[mid]가 같지 않으면 2 번의 비교 필요 (큰지 작은지)
  • 그러나 기계어로 표현되면 한 번으로 최적화 될 수 있음 → 함수 호출마다 한 번의 비교가 필요하다고 분석!
• 이진검색에서 최악의 경우: x가 배열에 있는 모든 원소보다 클 경우
  • floor 함수를 사용하면 뒷부분이 앞부분보다 클 수 있음
  • → 맨 마지막에 있거나, 아예 배열에 없을 때 가장 많은 비교 연산
• n이 2의 거듭제곱이면 그것의 반은 항상 짝수
  • → 최악의 경우 재귀 호출마다 n의 크기 정확하게 n/2로 감소

• 재현식 표현 (W: worst case)
  • $W(n) = W(\frac{n}{2}) + 1, W(1) = 1 (n ≥ 1)$
  • n을 2의 거듭제곱으로 제한하면, $W(n) = lg_n + 1$
  • n을 2의 거듭제곱으로 제한하지 않으면, $W(n) = ⌊lg_n⌋ + 1$   $∈ \; Θ(lg_n)$

Case 1) 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우 재현식

• n > 1이고, n = $2^k$ (k ≥ 1) ⇒ $lg^n = k$

$W(n) = W(\frac{n}{2}) + 1, W(1) = 1$
$\qquad\;\;\, = W(\frac{n}{n^2}) + 1 + 1 $
$\qquad\;\;\, = W(\frac{n}{2^3}) + 1 + 1 + 1$
$\qquad\;\;\; … $
$\qquad\;\;\, = w(1) + 1 + 1 + … + 1 $
$\qquad\;\;\, = 1 + k$
$\qquad\;\;\, = lg^n + 1$

• 복잡도 증명: $W(n) = lg^n + 1$ 임을 보임
  basis W(1) = $lg^1 + 1$ = 1
  hypothesis n이 $2^k$일 때, $W(n) = lg^n + 1$ 가정
  induction step 2n일 때도 $W(2n) = lg^{2n} + 1$ 을 만족함을 보임

$W(2n) = W(n) + 1$         (by 재현식)
$\qquad\quad\; = lg^n + 1 + 1$      (by hypothesis)
$\qquad\quad\; = lg^n + lg^2 + 1$
$\qquad\quad\; = lg^{2n} + 1$

Case 2) 일반적인 경우 - 반쪽 배열의 크기는 ⌊n/2⌋ 이 됨

n	왼쪽 부분배열 크기	mid	오른쪽 부분배열 크기
짝수	n/2 - 1	1	n/2
홀수	(n-1)/2	1	(n-1)/2

• 알고리즘이 각 단계에 찾아야 할 항목의 수는 기껏해야 ⌊n/2⌋ 개, 따라서
  $W(n) = 1 + W(⌊n/2⌋),\quad n > 1일 때$
  $W(1) = 1$

• 복잡도 증명: $W(n) = ⌊lg^n⌋ + 1$ (n ≥ 1인 정수)
  basis W(1) = ⌊lg^1⌋ + 1 = 1
  hypothesis n > m > 1인 정수 m에 대해 W(m) = ⌊lg^m⌋ + 1 가정
  induction step n에 대해 $W(n) = ⌊lg^n⌋ + 1$ 이 참임을 보임
  $W(n) = W(⌊\frac{n}{2}⌋) + 1$         (by 재현식)
  $\qquad\;\;\, = ⌊lg^{⌊\frac{n}{2}⌋}⌋ + 1 + 1$    (by hypothesis)

• 1) n이 짝수일 때
  $W(n) = ⌊lg^{\frac{n}{2}}⌋ + 1 + 1$
  $\qquad\;\;\, = ⌊lg^n - lg^2⌋ + 1 + 1$
  $\qquad\;\;\, = ⌊lg^n⌋ + 1$

• 2) n이 홀수일 때, $⌊\frac{n}{2}⌋ = \frac{n-1}{2}$
  $W(n) = ⌊lg^{\frac{n-1}{2}}⌋ + 1 + 1$
  $\qquad\;\;\, = ⌊lg^{n-1} - lg^2⌋ + 1 + 1$
  $\qquad\;\;\, = ⌊lg^{n-1}⌋ + 1$
  $\qquad\;\;\, = ⌊lg^n⌋ + 1$

---

🍰 합병 정렬

• 쌍방합병: 같은 순으로 정렬되어 있는 두 개의 배열을 정렬된 하나의 배열로 만드는 과정
• 합병을 반복적으로 적용하여 배열을 정렬할 수 있음

• 분할 : 배열을 n/2개의 요소로 구성된 2개의 부분 배열로 분할 → 요소가 한 개가 될 때까지 반복
• 정복 : 각 부분 배열 정렬
• 통합 : 정렬된 각 부분 배열을 하나의 정렬된 배열로 합병

MergeSort 알고리즘

• 문제: n개의 키를 오름차순으로 정렬
• 입력: 양의 정수 n, 배열 S[1..n]
• 출력: 오름차순으로 정렬된 배열

코드

void mergeSort(int n, keytype S[]) {
    if(n>1) {
        int h = floor(n/2), m = n - h;
        keytype U[1..h], V[1..m];
        copy S[1..h] to U[1..h];     // U : 앞부분
        copy S[h+1..n] to V[1..m];   // V : 뒷부분
        mergeSort(h, U);
        mergeSort(m, V);
        merge(h, m, U, V, S);
    }
}

---

Merge 알고리즘

• 문제: 오름차순으로 정렬되어 있는 두 개의 배열을 하나의 정렬된 배열로 합병
• 입력: 양의 정수 h, m, 오름차순으로 정렬된 배열 U[1..h], V[1..m]
• 출력: 오름차순으로 정렬된 배열 S[1..h+m]

코드

void merge(int h, int m, keytype U[], keytype V[], keytype S[]) {  // S: 최종 배열
    index i = 1, j = 1, k = 1;
    while(i ≤ h && j ≤ m) {   // 어느 한 배열의 요소 다 옮겨지면 while문 끝
        if(U[i] < V[j]) {
            S[k] = U[i];      // 작은 것부터 차례대로 배열 S에 삽입
            i++;
        }
        else {
            S[k] = V[j];
            j++;
        }
        k++;
    }
    if(i > h) copy V[j..m] to S[k..h+m];
    else copy U[i..h] to S[k..h+m];
    // U와 V 중 하나는 위 while문에서 모든 요소를 S에 삽입한 상태 
    // → 아직 요소가 남아있는 배열을 S에 삽입
}

예시

합병 알고리즘 최악의 경우

• 비교만 분석
• 기본연산: U[i]와 V[j]의 비교
• 입력 크기: h + m
• 최악의 경우
  • 한 번 비교에 하나의 요소가 새 배열로 복사되는 경우
  • h + m - 1번 비교하면 합병 완료됨
  • W(h+m) = h + m - 1

---

합병정렬 알고리즘 최악의 경우

• 기본연산: merge에서 일어나는 비교 연산
• 입력 크기: n, 배열 S의 크기
• 재현식: W(n) = W(h) + W(m) + u + m - 1;

• n이 2의 거듭제곱이면 h = m = n/2
  W(n) = W(n/2) + W(n/2) + n - 1 = 2W(n/2) + n - 1
  W(1) = 0

• 재현식의 해
  • n이 2의 거듭제곱으로 제한되면
    $W(n) = nlg^n - (n-1) ∈ Θ(nlg^n)$
  • n이 2의 거듭제곱으로 제한되지 않으면
    $W(n) = W(⌊\frac{n}{2}⌋) + W(⌈\frac{n}{2}⌉) + n - 1 ∈ Θ(nlg^n)$