2. Divide & Conquer

분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 

각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.

일반적인 재귀 호출과 다른점?

문제를 한 조각과 나머지로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

위 그림의 왼쪽은 문제를 n개의 조각으로 나눠 하나의 조각씩 해결하고 나머지 문제에 대해 반복하는 일반적인 재귀 호출을 나타내고,

오른쪽은 문제를 항상 절반씩으로 나누어 해결하는 분할 정복을 나타낸다.

분할 정복을 사용하는 알고리즘들은 대개 다음의 세개의 구성요소들을 가지고 있다.

1. 문제를 더 작은 문제로 분할하는 과정(divide)

2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

3. 더이상 문제를 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

분할 정복을 적용해 문제를 해결하기 위해서는 문제에 몇가지 특성이 있어야한다.

문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야하고, 

부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야한다.

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

1부터 n까지의 원소를 모두 더하는 문제를 생각해보자.

일반적인 재귀호출에서는 recursiveSum(...) 함수를 통해 한 번의 호출마다 하나의 원소를 더하는 해결 방법을 사용하였다.

분할 정복을 사용하기 위해서 1부터 n까지의 합을 반으로 나눠보자.

fastSum() = 1+2+3+...+n

  = (1+2+...+n/2) + ((n/2+1)+(n/2+2)+...+n)

위의 식에서 첫번째 부분 문제는 fastSum(n/2) 로 해결할 수 있지만

두번째 부분 문제는 '1부터 n까지의 합' 의 꼴이 아니라서 재귀 호출로 해결하기 어렵다.

따라서 두번째 부분 문제의 식을 다음과 같이 표현한다.

(n/2+1)+(n/2+2)+...+n = (n/2)+1+(n/2)+2+(n/2)+3+...+(n/2)+(n/2)

그러면 n/2 가 총 n/2번 더해져 있기 때문에 한 쪽으로 빼낼 수 있다.

따라서 n/2*n/2 + (1+2+....+n/2) 가 되어 n/2*n/2 + fastSum(n/2) 으로 해결 할 수 있게 된다.

따라서 전체 문제를 다음과 같이 나타낼 수 있다.

fastSum(n) = 2 * fastSum(n/2) + (n^2)/4 

이런 아이디어를 코드로 구현하면 다음과 같다.

// 1부터 n까지의 합을 구하는 분할 정복 알고리즘

int fastSum(int n){

//base case : n이 1일 때는 1을 리턴한다.

if(n == 1) return 1;

if(n % 2 == 1) return fastSum(n-1) + n;

return 2 * fastSum(n/2) + (n/2)*(n/2);

}

이때 n이 홀수인 경우에는 2로 딱 나누어 떨어지지않아 위의 식을 적용할 수 없기 때문에

n-1까지의 합을 구한 뒤 n을 더해주는 방식으로 문제를 해결한다.

recursiveSum() 함수는 n까지의 합을 구하기 위해 함수를 n번 호출해야 하지만,

fastSum() 함수는 함수 호출 두번에 한번 꼴로 n이 반씩 감소하기 때문에 일반적인 재귀 호출에 비해서 횟수가 현저히 감소한다는 것을 알 수 있다.

fastSum() 의 알고리즘의 수행시간은 약 O(logn) 정도 된다.

다음으로 n*n 크기의 행렬 A가 주어질 때 A의 거듭제곱을 계산하는 방법을 알아보자.

행렬의 곱셈에는 O(n^3)의 시간이 들기 때문에 A^m을 계산하기 위해서는 O(n^3*m) 번의 연산이 필요하게 된다.

그러면 n과 m의 크기가 커지면 컴퓨터로 계산하기 힘든 수치가 되어버린다.

분할정복으로 A^m을 구하는 방법도 합을 구하는 방법과 비슷하게 A^m을 구하는 과정의 m개의 조각을 반으로 나누는 데서 시작한다.

A^m = A^(m/2) * A^(m/2)

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

class SquareMatrix;  // 정방행렬을 표현하는 SquareMatrix 클래스가 있다고 가정하자.

SquareMatrix identity(int n); // n*n 크기의 항등행렬을 리턴하는 함수

SquareMatrix pow(const SquareMatrix& A, int m){

// base case : A^0 = 1

if(m == 0) return identity(A.size());

// m이 홀수인경우 A^m = A^(m-1) * A

if(m % 2 > 0) return pow(A, m-1) * A;

SquareMatrix half = pow(A, m/2);

return half * half;

}

위의 코드에서 m이 2로 나누어 떨어지지 않을 때, 즉 m이 홀수일 때 m을 절반과 가깝게 나누지 않고 A^(m-1) * A 로 나누는 것을 볼 수 있다.

대부분의 분할 정복 알고리즘은 가능한 절반에 가깝게 문제를 나누고자 한다.

그러나 이 문제에서는 그렇게 나누는 것이 더 비효율적이다.

위의 사진에서 보면 pow(A,7)을 pow(A,3)과 pow(A,4)로 나누는 경우 두 함수 모두 pow(A,2)를 호출하게 된다.

그러면 pow(A,2)를 중복되게 호출하게 됨으로써 비효율적이고 시간이 더 오래걸리게 된다.

따라서 밑의 방식으로 m이 홀수일 때는 pow(A, m-1) 을 호출하는 방법을 사용하여 중복 호출을 줄이도록 한다.