2장. 분할 정복법 (Divide & Conquer)

◆ 분할 정복식 설계 전략

큰 문제를 작은 문제로 나누어 해결한 후, 해답을 모아 큰 문제의 해를 만드는 방법

문제의 성질과 전체 형태가 작은 문제에서도 똑같이 유지 됨 <-- 재귀적인 형태도 가능!

 

분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.

정복(Conquer): 나눈 작은 문제를 각각 해결한다. 

통합(Combine): (필요하다면) 해결된 해답을 모은다.

 

이러한 문제 해결 방법을 하향식(top-down)  접근 방법이라고 한다.

 

---

◆ 바닥 함수와 천장 함수

 

바닥 함수: 실수 x에 대해, x보다 작거나 같은 정수 중 가장 큰 정수

 

천장 함수: 실수 x에 대해, x보다 크거나 같은 정수 중 가장 작은 정수

 

 

 

 

---

◆ 이분 검색 (binary search)

배열을 반으로 나눠서, 찾아야할 x와 location을 비교해 location을 옮겨감

재귀적 방식으로 진행함

 

✓ 분할 : 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고,

그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다.

✓ 정복 : 선택된 반쪽 배열에서 x를 찾는다.

✓ 통합 : 없음

 

※ 입력 파라미터 n, S, x는 수행중 변하지 않는 값이므로, 재귀 호출시마다 계속 갖다니면 낭비! 얘네를 전역변수로 지정하고, 재귀 호출 시에는 인덱스만 넘겨줄 수 있음. ※ 반복 알고리즘이 재귀 알고리즘보다 상수적으로 계산이 빠름. (계산 복잡도가 좋다는 건 아님)

 

---

◇ 이분 검색 코드

index location(index low, index high){
    index mid;

    if (low > high) //데이터가 없는 경우
        return 0;
    else{
        mid = (low + high) / 2; //중간 값 갱신
        if (x == S[mid]) //key를 찾은 경우
            return mid;
        else if (x < S[mid]) //key가 중간값보다 작은 경우
            return location(low, mid - 1); //왼쪽 배열 반 선택
        else //key가 중간값보다 큰 경우
            return location(mid + 1, high); //오른쪽 배열 반 선택
    }
}

 

---

◇ 이분 검색 - 최악의 경우 시간 복잡도 분석

• 단위연산 : x와 S[mid]의 비교
• 입력크기 : 배열의 크기 n

 

이분 검색에서 최악의 경우는, 검색하게 될 반쪽 배열의 크기가 항상 정확히 절반이 되는 경우이다.

 

W(n) 을 n에 대한 Worst Case의 시간 복잡도 함수라 하자.

 

아래와 같이 W에 관한 식이 W로 또 표현되는 걸 재현식, 연쇄식이라 함

배열의 크기가 n인 경우의 비교 횟수는, 배열의 크기가 n/2인 경우의 비교횟수 + 처음 비교횟수 1번이라는 뜻

 

이러한 재현식의 해는, W(1) = 1인 성질을 가지고 대입해가며 풀거나

아래와 같이 반복 대입법을 통해 구할 수 있다.

 

ㆍ반복 대입법 : W를 W에 대입하여 규칙을 찾는 방법

n =1 인 경우에도 x와 S[mid]가 같은지 한번 비교하기 때문에, W(1) = 1

 

---

◆ 합병 정렬 (merge sort)

쪼갰다가 정렬하면서 합쳐서 올라오기

 

데이터의 개수가 1보다 크면 S[1]부터 S[h]까지(절반)을 U에다 복사 S[h+1]부터 S[n]까지(남은 절반)을 V에다 복사 Mergesort(h,U)가 종료되면 정렬된 U가 얻어질 것이고 Mergesort(m,V)가 종료되면 정렬된 V가 얻어질 것! 그러고나면 merge(h,m,U,V,S)로 얘네를 합치면서 정렬하면 댐

 

 

<과정>

 

---

◇ 합병 정렬 코드

void mergesort(int n, keytype S[]){
    const int h = n/2, m = n - h; // 반씩 나눔
    keytype U[1..h], V[1..m]; // U, V
    
    if (n > 1){	// 데이터의 개수가 1보다 크면
        copy S[1...h] to U[1...h]; // S[1~h]를 U로 복사
        copy S[h+1...n] to V[1...m]; // S[h+1~n]을 V로 복사
        mergesort(h, U); // U에서 mergesort 재귀 --> 정렬된 U가 나옴
        mergesort(m, V); // V에서 mergesort 재귀 --> 정렬된 V가 나옴
        merge(h, m, U, V, S); // 각각 정렬된 U,V를 다시 합침
    }
}

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]){
    index i, j, k;	// U[i], V[j], S[k]
    i = 1; j = 1; k = 1;	// 1로 초기화
    while (i <= h && j <= m){ // 
        if (U[i] < V[j]){ // U의 데이터가 V의 데이터보다 작으면
            S[k] = U[i]; // U의 데이터를 S로 복사
            i++; // U의 인덱스 증가
        }
        else{ //V의 데이터가 U의 데이터보다 작으면
            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로 복사
}​

---

◇ 합병 정렬 - 최악의 경우 시간 복잡도 분석

 

■ merge 함수

• 단위연산 : merge 함수에서의 U[i]와 V[j]의 비교
• 입력크기 : h와 m

merge 함수에서 최악의 경우는, 합병시 U, V 데이터를 하나씩 번갈아가며 합친 경우이다.

즉, i = h + 1이고, j = m인 상태로 루프를 빠져나가는 경우가 최악이다.

 

이때 단위연산의 시행 횟수는 h + m - 1이다.

따라서 W(h,m) = h + m -1

 

 

■ mergesort 알고리즘

• 단위연산 : merge()에서 발생하는 비교
• 입력크기 : S의 데이터의 개수인 n

mergesort 알고리즘에서 최악의 경우는, U를 정렬하는 데 걸리는 시간 + V를 정렬하는 데 걸리는 시간 + 합병하는 데 걸리는 시간이 젤 오래 걸리는 경우이다. 즉, W(h) + W(m) + h + m -1이다. 이때 h와 m은 n/2이므로, W(n) = 2W(n/2) + n - 1이라 할 수 있다.

 

 

▽ 이정돈 유도할 수 있어야 함

입력 크기가 1이면 비교 자체를 안 들어가므로 W(1) = 0

 

---

◇ 합병 정렬 - 공간 복잡도 분석

합병 정렬은 입력 배열S 외에, U와 V를 추가로 만들어서 사용하기 때문에, 제자리 정렬이 아님

※ 제자리 정렬(in-place sort) 알고리즘이란? 추가적인 저장 장소를 사용하지 않고 정렬하는 알고리즘

 

다음 재귀 호출에는 n/2의 추가적인 저장 장소가 필요하므로, 필요한 총 저장 장소의 크기는 다음과 같다.

즉 2n만큼의 추가 저장 장소가 필요함!

 

---

◇ 공간 복잡도가 향상된 합병 정렬

합병 정렬이 제자리 정렬이 될 수는 없지만, 2n만큼 요구되는 추가 저장 장소를 n만큼으로 줄일 수는 있음.

 

S에서 인덱스를 사용해 반절, 반절 나눠서 U에다 정렬하며 옮겨쓴 후, 끝나기 직전에 U를 다시 S에다 옮겨 적음

 

그림에서 A가 모두 정렬된 후 B를 정렬함. 이때 A에서 사용이 끝난 추가 공간을 재사용할 수 있음. 

일단 나눠놓고 나중에 복사하는 방식!

앞에서는 맨 끝단이 정렬될 때까지 쭉 공간을 붙잡고 있었지만,

이 방법은 중간중간 메모리를 반납하면서 사용하기 때문에 공간적 측면에서 더 효율적임.

 

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; //U[i], U[j], S[k]
    keytype U[low...high];
    i = low; 
    j = mid + 1; 
    k = low;
    while (i <= mid && j <= high){	// U 왼쪽과 오른쪽에 비교할 데이터가 남았다는 뜻
    
        if (S[i] < S[j]){ // 각각 정렬된 상태
            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로 복사
}

 

 

---

◆ Quick sort

파티션 → 퀵소트(피봇왼쪽) →퀵소트(피봇오른쪽)
파티션은 : pivotpoint보다 작은 것/큰 것으로 배열을 분리할 수 있도록 하는 pivotpoint의 자리 찾기

 

partition(low, high, &pivotpoint) 함수에서 pivotitem과 S[i]를 하나씩 비교. pivotitem > S[i]인 경우가 나오면 pivotpoint++ 하고, S[i]와 S[pivotpoint] 바꾸기 끝까지 가면 pivotpoint 인덱스 리턴 (이때 pivotitem과 S[pivotpoint] 바꾸면, pivotitem 기준 왼쪽/오른쪽 분리됨)

quicksort는 아래와 같이 분할 정복 방법을 따름.

 

quick sort의 경우, 동일한 값이 있을 경우 정렬 후 그 값들끼리 순서가 유지되지 않는 Unstable Sort이다.

 

---

◇ Quick sort  코드

void quicksort (index low, index high) {
index pivotpoint;
if (high > low) {  // 적어도 데이터가 2개일 때
    partition(low,high,pivotpoint);  // pivotpoint의 적절한 위치를 잡아서 레퍼런스로 돌려줌
    quicksort(low,pivotpoint-1);	// pivotpoint 왼쪽부분 quicksort
    quicksort(pivotpoint+1,high);	// pivotpoint 오른쪽부분 quicksort
    }
}

 

partition()을 통해 pivotpoint의 적절한 위치를 잡아서 레퍼런스로 돌려줌

void partition (index low, index high, index& pivotpoint){
    index i, j;
    keytype pivotitem;
    pivotitem = S[low];	// 맨 왼쪽에 있는 데이터를 pivotitem으로 설정
    j = low; // j를 맨 왼쪽 데이터로 초기화. j는 잠재적 pivotpoint
    for (i = low + 1; i <= high; i++){	// i는 젤 왼쪽 다음~ 젤 오른쪽까지
        if (S[i] < pivotitem){	// S[i]가 현재 pivotitem보다 작으면,
            j++;	// j 하나 증가 (S[i] 들어갈 자리 하나 확보)
            exchange S[i] and S[j];	//S[i] <-> S[j] 해서 S[i]를 앞쪽으로 옮김
        }
    } //j: pivotitem 보다 작은 그룹의 제일 우측 끝 데이터의 위치
    pivotpoint = j;	// 반환할 pivotpoint 인덱스 위치 설정
    exchange S[low] and S[pivotpoint]; // 현재 pivotitem 값을 pivotpoint(올바른 위치임)에 넣어준다. 
}

 

#include <iostream>

using namespace std;

int S[8] = { 15, 22, 13, 27, 12, 10, 20, 25 };

void partition(int low, int high, int& pivot) {
    //pivot의 위치 잡아서 돌려주기
    pivot = low;
    int pivotitem = S[pivot];

    for (int i = low + 1; i <= high; i++) {
        if (S[i] < pivotitem) {
            pivot++;
            int temp = S[i];
            S[i] = S[pivot];
            S[pivot] = temp;
        }
    }
    
    int temp = S[low];
    S[low] = S[pivot];
    S[pivot] = temp;
}


void quicksort(int low, int high) {
    if (low < high) {
        int pivot;
        partition(low, high, pivot);
        quicksort(low, pivot - 1);
        quicksort(pivot + 1, high);
    }
}


int main() {
    quicksort(0, 7);
    
    for (int i = 0; i < 8; i++) {
        cout << S[i] << " ";
    }

    return 0;
}

 

---

◇ Quick sort  - 시간 복잡도 분석

 

■ partition 함수

• 단위연산 : S[i]와 pivotitem의 비교
• 입력크기 : high-low+1

partition 함수에서는 입력 배열의 첫 항목 빼고 나머지 항목을 한번씩 비교하므로, T(n) = n-1 이다.

 

 

■ quicksort 알고리즘

• 단위연산 : partition 알고리즘의 S[i]와 pivotitem의 비교
• 입력크기 : 배열 S의 총 항목 수인 n

quicksort 알고리즘에서 최악의 경우는, 입력 배열이 이미 비내림차순으로 정렬되어 있는 경우이다. 

즉 n 크기의 분석을 한 다음 차례에 n-1개의 분석을 해야 함.

따라서 T(n) = T(n-1) + n-1 이다. 이 재현식을 풀면 다음과 같다.

따라서 quicksort 알고리즘의 최악의 시간 복잡도 W(n) = n(n-1)/2 이다.

 

 

 

참고) 최선의 경우는, 문제가 매번 반씩으로 나누어질 때를 의미한다.

그때의 시간 복잡도 함수는 아래와 같다.

 

---

◆ 행렬 곱셈 (matrix multiplication)

단순한 행렬 곱셈 알고리즘은 행렬의 크기가 커질수록 계산량이 많아지므로 다른 방법이 필요함

 

여기서는 행렬의 곱셈을 어떻게 빨리 하느냐가 아니라, 어떻게 분할정복법으로 적용할 수 있는지 알아볼 것임

 

---

◇ 단순한 행렬 곱셈 코드

void matrixmult (int n, const number A[][], const number B[][], number C[][]) { 
	// nxn 행렬인 A,B를 곱해서 C를 출력
        index i, j, k; 
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                C[i][j] = 0;	// 일단 계산전에 0으로 초기화
                    for (k = 1; k <= n; k++)
                        C[i][j] = C[i][j] + A[i][k] * B[k][j];	// 행렬 곱셈
            }
    	}
}

 

---

◇ 단순한 행렬 곱셈 - 시간 복잡도 분석

 

■ 곱셈 기준

• 단위연산 : 맨 안쪽 루프의 곱셈 연산
• 입력크기 : n

모든 경우 시간 복잡도는 총 곱셈 횟수(한자리에 필요한 곱셈 * 행 개수 * 열 개수)이므로, T(n) = n * n * n = n³

 

 

■ 덧셈/뺄셈 기준

• 단위연산 : 맨 안쪽 루프의 덧셈 연산
• 입력크기 : n

모든 경우 시간 복잡도는 총 덧셈 횟수(한자리에 필요한 덧셈 * 행 개수 * 열 개수)이므로, T(n) = (n-1) * n * n = n³ - n²

 

 

ex) 2x2 행렬

--> 총 8번의 곱셈과 4번의 덧셈이 필요함.

 

---

◆ 행렬 곱셈 - 쉬트라센 방법 (Strassen Algorithm)

행렬 곱셈에서 덧셈, 뺄셈을 늘리는 대신에 곱셈 횟수를 하나 줄인 방법

위와 같이 2x2행렬 곱셈이 주어졌을 때, 쉬트라쎈(Strassen)의 해는 다음과 같다.

여기서 각 원소는 아래와 같이 표현됨

2x2 행렬 곱셈시, 7번의 곱셈과 18번의 덧셈(뺄셈)이 필요함.

 

언뜻 봐서는 별로지만, 행렬 크기가 어느정도 이상으로 커지면 좋아진다!

 

---

◇ 행렬 곱셈 - 쉬트라쎈 방법 코드

void strassen (int n, n*n_matrix A, n*n_matrix B, n*n_matrix& C){
    if (n <= threshold)	// n이 임계점보다 작은 경우
        단순한 알고리즘을 사용하여 C = A * B를 계산
    else {
        A를 4개의 부분행렬 A11, A12, A21, A22로 분할
        B를 4개의 부분행렬 B11, B12, B21, B22로 분할
        쉬트라센 방법을 사용하여 C = A * B를 계산
        // 되부르는 호출의 예: strassen(n/2, A11+A22, B11+B22, M1)
    }
}

 

n이 2의 거듭제곱인 nxn 행렬에서, 다음과 같이 나눠서 진행함.

※ 행렬의 크기가 2의 거듭제곱이 아닌 경우에는, 크기를 맞추기 위해 필요한 만큼 0을 넣어서 푼다.

 

---

◇ 행렬 곱셈 - 쉬트라쎈 시간 복잡도 분석

 

■ 곱셈 기준

• 단위연산: 곱셈 연산
• 입력크기: 행과 열의 수, n

임계값을 1이라 하자. 재현식은 다음과 같다.

이 식을 전개해보면,

따라서 T(n) ∈ Θ(n^2.81) 이다. 

 

 

■ 덧셈/뺄셈 기준

• 단위연산: 덧셈/뺄셈 연산
• 입력크기: 행과 열의 수, n

임계값을 1이라 하자. 재현식은 다음과 같다.

이 식을 정리해보면,

따라서 T(n) ∈ Θ(n^2.81) 이다. 

 

---

◇ 단순 행렬 곱셈 vs 쉬트라쎈 시간복잡도 비교

임계점(두 알고리즘의 효율성이 교차하는 시점)을 넘어가면, 쉬트라센 알고리즘이 단순한 곱셈 알고리즘보다 효율적!!

 

---

◆ 큰 정수의 곱셈

보통 n자리수의 두 숫자를 곱하는 데 걸리는 시간은 n². 즉 2차 시간이 걸림

이걸 1차 시간만 걸리도록 만들 수 있음!

 

u * v를 계산한다고 하자. u와 v를 다음과같이 표현함

← n자리 수인 u를, ⌈n/2⌉자리 수인 x와   ⌊n/2⌋자리 수인 y로 표현

 

이렇게 곱하면 1차 시간에 수행하는 셈이다.

 ⎣n/2⎦

---

◇ 큰 정수의 곱셈 코드

large_integer prod(large_integer u, large_integer v){ 
    large_integer x, y, w, z;
    int n, m;
    n = maximum(u의 자리수, v의 자리수); 
    if(u == 0 || v == 0) 
    	return 0;
    else if( n <= threshold)
    	return 일반적인 방법으로 구한 u × v ; 
    else{
    	m = ⎣n/2⎦;
        x = u divide 10m; y = u mod 10m; 
        w = v divide 10m; z = v mod 10m; 
        return prod(x, w) × 10^(2m) + (prod(x, z)+prod(w, y)) × 10^m + prod(y, z);
	}
}

prod 안에서 prod를 4번 불러서 수행함.

 

근데 사실..

이때도 최악의 경우 시간복잡도 W(n) ∈ Θ(n²)이라, 원래 방법과 비교했을 때 노이득임

 

---

◇ 큰 정수의 곱셈 - 개선 ver 

r 계산을 추가해 곱셈 한번을 줄여주는 방법

이것도 분할 정복으로

큰 자리수 곱셈 문제를 쪼개서 작은 자리수 곱셈 문제로 해결한 후 전체 문제를 처리하는 방식임

 

<방법>

r에서 xz+yw를 한번에 구해서 전개식에 대입하면 곱셈 횟수를 한번 줄일 수 있음.

 

---

◇ 큰 정수의 곱셈 - 개선 ver 코드

large_integer prod2(large_integer u, large_integer v){ 
    large_integer x, y, w, z, r, p, q;
    int n, m;
    n = maximum(u의 자리수, v의 자리수); 
    if(u == 0 || v == 0) 
    	return 0;
    else if( n <= threshold)
    	return 일반적인 방법으로 구한 u × v ; 
    else{
        m = ⎣n/2⎦;
        x = u divide 10m; y = u mod 10m; 
        w = v divide 10m; z = v mod 10m; 
        r = prod2(x+y,w+z);
        p = prod2(x, w); 
        q = prod2(y, z);
        return p×10^(2m) + (r–p-q)×10^m + q; // p = zw //  r-p-q = xz + yw //  q = yz
    }
}

prod 안에서 prod를 3번 불러서 수행함

최악의 경우 시간복잡도 W(n) ∈ Θ(n^(1.58)) 정도에 속함. 굿

 

---

◆ 분할 정복법을 사용하지 말아야 하는 경우

1) 시간복잡도가 Θ(2ⁿ) 형태인 경우

- 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우

 

2) 시간복잡도가 Θ(n^lg n)의 형태인 경우

- 크기가 n인 입력이 n개 이상의 조각으로 분할되며, 분할된 부분의 크기가 n/c인 경우

 

---

◆ 도사 정리

T(n) = aT(n/b) + f(n)일 때 시간 복잡도 함수를 쉽게 구하는 법.

T(n) = aT(n/b) + f(n)이고, nlogb a = g(n)이라 하자

이때, 다음 내용을 만족한다.

1. g(n)이 더 무거우면 g(n)이 수행 시간을 결정함
2. f(n)이 더 무거우면 f(n)이 수행 시간을 결정함
3. g(n)과 f(n)이 같은 차수면 g(n)에 log n을 곱한 것이 수행 시간이다

 

관련 공식)

 

예시)

 

참고)

T(n) ≤ aT(~~) 이면 O()로 표현

T(n) ≥ aT(~~) 이면 Ω()로 표현