분할정복 (Divide and Conquer)

분할 정복 (Divide and Conquer)

7.1 도입

분할 정복은 가장 유명한 알고리즘 디자인 패터다임

• 각개 격파라는 말로 간단히 설명 할 수 있음

분할 정복과 재귀 호출의 다른 점

• 재귀 호출 : 한 조각과 나머지 전체로 나눔
• 분할 정복 : 거의 같은 부분 문제로 나눔

분할 정복 알고리즘의 세가지 구성요소

• 문제를 더 작은 문제로 분할하는 과정(divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
• 더 이상 답을 분할 하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

예제 : 수열의 빠른 합과 행렬의 빠른 제곱

• 1부터 n까지의 합을 n개의 조각으로 나눈 뒤, 
  이들을 반으로 뚝 잘라 n/2개의 조각들로 만들어진 부분 문제 두 개를 만듬

• faseSum() 
  = 1+2+…+n 
  = ( 1+2+…+n/2 ) + ((n/2+1)+…+n)

코드 7.1

// 필수조건 : n은 자연수  
// 1+2+...+n 을 반환한다.   
int fastSum(int n){  
  // 기저 사례  
  if(n == 1) return 1;  
  if(n%2 == 1) return fastSum(n-1) + n;  
  return 2*fastSum(n/2) + (n/2) * (n/2);  
}

시간 복잡도 분석

• O(lgn)

행렬의 거듭 제곱

• n*n 크기의 행렬 A 가 주어질 때, A의 거듭제공(power) A^m은 A를 연속해서 m번 곱한 것

코드 7.2 행렬의 거듭 제곱을 구하는 분할 정복 알고리즘

// 정방 행렬을 표현하는 SquareMatrix 클래스가 있다고 가정하자.
Class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
// A^m을 반환한다.
SquareMatrix pow(const SquareMatrix& A, int m){  
    // 기저 사례 : A^0=I
    if(m == 0) return identity(A.size());
    if(m % 2 > 0) return pow(A, m-1) * A;
    SquareMatrix half = pow(A, m /2 );
return half * half;

시간 복잡도

• 곧이곧대로 m-1번 곱셈을 통해 A^m을 구하면 O(n^3m)번의 연산이 필요함.
• 분할 정복을 사용할 경우은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커짐.
• 그림 7.2 참고, a는 m-1번 곱한것과 다를게 없음. b는 O(lgm)
• 분할정복이 큰 효율 저하는 불러오는 이유는 바로 여러번 중복되어 계산되면서 시간을 소모하는 부분이 있기 때문

예제 : 병합 정렬과 퀵정렬

• 병합정렬 
  주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀호출을 이용해 각가 정렬함. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻음.

• 퀵정렬 
  배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분한 함. 
  이를 위해 퀼 정렬은 파티션(partition)이라고 부르는 단계를 도입하는데, 
  이는 배열에 있는 수 중 임의의 ‘기준수(pivot)’를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽 더 큰 숫자를 오른 쪽으로 보내는 과정임

• 두 정렬 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐 병합 단계에서 하느냐가 다름.

시간복잡도 분석

• 병합정렬 
  병합에 필요한 시간 * 단계별로 필요한 시간 
  O(n) * O(lgn) = O(nlgn)

• 퀵정렬 
  시간복잡도를 구하기 까다로움 - 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없음. 
  최악의 경우 O(n^2) 
  평균 O(nlgn)

예제 : 카라츠바의 빠른 곱셈 알고리즘

시간 복잡도 분석

• 단순한 알고리즘 O(n^2)
• 빠른 곱셈 알고리즘 O(n^lg3)