[알고리즘 분석] 2장. 분할정복법(divide-and-conquer) (1)

1. 분할정복법: 큰 문제를 작은 문제로 나누고 작은 문제의 해를 통해 큰 문제의 해를 구하는 방식

- 큰 문제의 형태가 작은 문제의 형태와 동일함 -> 재귀적 방법 많이 사용한다.

분할정복(divide-and-conquer)식 설계 전략
- 분할(divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
- 정복(conquer): 나눈 작은 문제를 각각 해결한다.
- 통합(combine): 해결된 해답을 모은다. (필요 시)

-> 하향식 접근 방법 (Top-down)

 

2. 이분검색(binary search): 재귀적 방식

[설계 전략]
- x(key)가 배열의 중간에 위치하고 있는 항목과 같으면, x 찾음
- 그렇지 않다면 분할 정복법을 이용하여 해를 찾음
- 분할: 배열을 반으로 나누어 x(key)가 중앙에 위치한 S[mid]보다 작으면 왼쪽 배열 반을 선택하고, 크면 오른쪽 배열 반을 선택한다.
- 정복: 선택된 반쪽 배열에서 x를 찾는다.
- 통합: 이 알고리즘에서는 필요하지 않음

index location(index low, index high){
    index mid;
    // 배열의 크기 n, 배열 S, 키 x는 변하지 않는 값이므로 전역변수로 지정
    if (low > high) //데이터가 없음, 찾지 못함
        return 0;
    else{
        mid = (low + high) / 2; //중앙 값
        if (x == S[mid]) //찾음
            return mid;
        else if (x < S[mid]) //분할
            return location(low, mid - 1); //왼쪽 배열 반 선택
        else //분할
            return location(mid + 1, high); //오른쪽 배열 반 선택
        // 꼬리 재귀호출: 모든 재귀호출이 알고리즘의 마지막 부분에서 이루어짐 
        // -> 반복 알고리즘 변환이 쉬움
    }
}

[최악의 경우 시간복잡도 분석]
- 단위연산: x와 S[mid]의 비교 -> 조건문을 2번 수행하지만 사실상 비교는 한 번 이루어진다고 봐도 무방하다.
- 입력크기: 배열의 크기 n(high - low + 1)
1) 검색하게 될 반쪽 배열의 크기가 항상 정확하게 $ \frac{2}{n} $ 이 되는 경우
$ W(n) = W(\frac{n}{2}) + 1, \ n > 1, \ n = 2^{k} \ (k \geq 1), \ W(1) = 1 $
-> 재현식(W를 표현하기 위한 식을 W로 표현)
-> $ W(\frac{n}{2}) $ : 다음으로 검색(배열의 크기 n이 절반으로 줄어든다.)
-> +1 : 같은지 큰지 작은지 비교 연산

반복 대입법을 통해 시간 복잡도를 계산해보면, 
$ W(n) = W(\frac{n}{2}) + 1 $
$ = (W(\frac{n}{2^2}) + 1) + 1 $
$ = W(\frac{n}{2^2}) + 2 $
$ = (W(\frac{n}{2^3}) + 1) + 1 $
...
$ = W(\frac{n}{2^k}) + k, \ (n = 2^k) $
$ = W(1) + k = 1 + k $
$ k = lg \ n $
$ W(n) = 1 + lg \ n $ 으로 나타낼 수 있다.

[추정 후 증명 - 수학적 귀납법]
1) 귀납 출발: n = 1이면, W(1) = lg1 + 1 = 1 이므로 성립한다.
2) 귀납 가정: $ n = 2^{k}, \ k \geq 1 $ 에 대해 W(n) = lg n + 1이라고 가정한다.
3) 귀납 단계: W(2n) = lg(2n) + 1을 증명하면 된다.
W(2n) = W(n) + 1 (앞서 구한 재현식에 의해)
W(n) = lg n + 1 이라고 가정했으므로
W(2n) = lg n + 1 + 1
W(2n) = lg n + lg 2 + 1 ( lg 2 == 1)
W(2n) = lg 2n + 1 성립

 

3. 합병정렬(mergesort)

- 문제: n개의 정수를 비내림차순으로 정렬하시오.
- 입력: 정수 n, 크기가 n인 배열 S[1...n]
- 출력: 비내림차순으로 정렬된 배열 S[1...n]
- 보기: 27, 10, 12, 20, 25, 13, 15, 22

void mergesort(int n, keytype S[]){
    const int h = n/2, m = n - h; // 반씩 나눔
    keytype U[1..h], V[1..m]; // 새로운 배열 
    
    if (n > 1){
        copy S[1...h] to U[1...h]; //S의 반을 U로 복사
        copy S[h+1...n] to V[1...m]; //S의 나머지 반을 V로 복사
        mergesort(h, U); // 복사된 반에서 또 mergesort 수행
        mergesort(m, V);
        merge(h, m, U, V, S); // 나눠진 배열 다시 합침
    }
}

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]){
    index i, j, k;
    i = 1; j = 1; k = 1;
    while (i <= h && j <= m){ //U와 V에 비교할 데이터가 존재
        if (U[i] < V[j]){ // U의 데이터가 더 작음
            S[k] = U[i]; // U의 데이터를 S로 복사
            i++; // U의 인덱스 증가
        }
        else{ //V의 데이터가 더 작음
            S[k] = V[j]; //V의 데이터를 S로 복사
            j++; //V의 인덱스 증가
        }
        k++; //S의 인덱스 증가
    }
    if (i > h) //U의 데이터가 모두 S로 옮겨감 -> V의 데이터 남음
        copy V[j...m] to S[k...h+m]; // V의 남은 데이터들 고대로 S로 복사
    else //V의 데이터가 모두 S로 옮겨감 -> U의 데이터 남음
        copy U[i...h] to S[k...h+m]; // U의 남은 데이터들 고대로 S로 복사(U, V는 이미 정렬되어 있음)
}​

[합병 알고리즘(merge)의 최악의 경우 시간복잡도 분석]
- 단위연산: U[i]와 V[j]의 비교
- 입력 크기: h와 m
i = h+1이고 j = m 인 상태로 while문을 빠져나오는 때가 최악의 경우이다.
W(h, m) = h + m - 1
i와 j의 증가한 횟수가 단위연산의 실행횟수와 동일하다 
- i: 1 -> h + 1: h번 증가
- j: 1 -> m: m-1번 증가
따라서 W(h, m) = h + m -1이 최악의 경우 시간복잡도이다.

[합병 정렬 알고리즘(mergesort)의 최악의 경우 시간복잡도 분석]
- 단위연산: merge에서 발생하는 비교
- 입력 크기: n
W(h, m) = W(h) + W(m) + h + m - 1
W(h): U를 정렬하는 데에 걸리는 시간
W(m): V를 정렬하는 데에 걸리즌 시간
h + m - 1: 앞서 합병 알고리즘에서의 최악의 경우 시간복잡도
정수 $ n = 2^{k}, \ k \geq 1 $ 이라고 가정하면 $ h = \frac{n}{2}, \ m = \frac{n}{2} $이 된다. (n이 2의 거듭제곱이므로 딱 나눠짐)
따라서 $ W(n) = W(\frac{n}{2}) + W(\frac{n}{2}) + \frac{n}{2} + \frac{n}{2} - 1 $
$ W(n) = 2W(\frac{n}{2}) + n - 1 $
$ W(1) = 0 $
$ W(n) = 2(2W(\frac{n}{2^2}) + \frac{n}{2} - 1) + n - 1 $
$ = 2^2W(\frac{n}{2^2}) + (n-2) + (n-1) $
$ = 2^2(2W(\frac{n}{2^3})) + (n-2^2) + (n-2) + (n-1) $
...
$ = 2^kW(\frac{n}{2^k}) + n-2^{k-1} + n-2^{k} + ... + n-1 $
$ = 2^kW(1) + (k-1)n - (2^0 + 2^1 + 2^2 + ... 2^{k-1}) $
$ = n + (k-1)n - \frac{2^k - 1}{2 - 1} $
$ = kn - (2^k - 1) $
$ k = lg \ n $ 이므로
$ W(n) = nlg\ n - (n - 1) $
즉, $ W(n) \in \Theta(nlg\ n) $ 이다.

n이 2의 거듭제곱이 아닐 때 -> 구하기 복잡..
어차피 같은 카테고리이므로 그냥 n이 2의 거듭제곱이라고 가정하고 풀어도 점근적으로 같은 해를 얻을 수 있다.

[공간복잡도 분석]
- 합병 정렬 알고리즘은 제자리정렬 알고리즘이 아님! -> S이외에 U와 V의 새로운 배열을 추가로 만들어야 함
* 제자리정렬 알고리즘(in-place sort): 추가적인 저장장소를 사용하지 않고 정렬하는 알고리즘
- S의 크기가 n이면, U와 V의 저장장소 크기의 합이 n이 되고, 다음 재귀 호출에는 그 반인 $ \frac{n}{2} $ 이 된다.
$ n + \frac{n}{2} + \frac{n}{4} + ... = \frac{n}{1-\frac{1}{2}} = \frac{n}{\frac{1}{2}} = 2n $
$ 2n \in \Theta(n) $

[향상된 공간복잡도를 가진 합병정렬 알고리즘]
- 입력: 정수 n, 크기 n인 배열 S[1...n]
- 출력: 비내림차순으로 정렬된 배열 S[1...n]

void mergesort2(index low, index high){
    index mid;
    if (low < high){
        mid = (low + high) / 2;
        mergesort2(low, mid);
        mergesort2(mid + 1, high);
        merge2(low, mid, high);
    }
}

void merge2(index low, index mid, index high){
    index i, j, k; keytype U[low...high];
    i = low; j = mid + 1; k = low;
    while (i <= mid && j <= high){
        if (S[i] < S[j]){ //S는 반씩 정렬되어 있음
            U[k] = S[i]; //U에 S정렬
            i++;
        }
        else{
            U[k] = S[j];
            j++;
        }
        k++;
    }
    if (i > mid) //S의 왼쪽 부분이 다 U에 복사됨 -> 오른쪽 부분이 남음
        copy S[j...high] to U[k...high]; //S에 남은 오른쪽 부분을 U에 복사
    else //S의 오른쪽 부분이 다 U에 복사됨 -> 왼쪽 부분이 남음
        copy S[i...mid] to U[k...high]; //S에 남은 왼쪽 부분을 U에 복사
    copy U[low...high] to S[low...high]; //U에 정렬된 데이터들을 S로 복사
}

- 공간복잡도는 n으로 줄일 수 있음