07 분할 정복

계속 수정됩니다.

분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.

재귀 호출과의 차이는 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

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

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

분할 정복을 적용하려면 문제에 몇 가지 특성이 성립해야 한다.

• 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
• 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

분할 정복은 많은 경우 같은 작업을 더 빠르게 처리해 준다.

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

$1+2+…+n$의 합을 재귀 호출을 이용해 계산하는 recursiveSum() 함수를 작성했었는데,
여기서는 분할 정복을 이용해 똑같은 일을 하는 fastSum() 함수를 만들어 보자.

1부터 n 까지의 합을 n개의 조각으로 나눈 뒤,
이들을 반으로 뚝 잘라 $\frac{n}{2}$개의 조각들로 만들어진 부분 문제 두 개를 만든다.
(편의상 n은 짝수라고 가정한다.)

$fastSum()=1+2+…+n$

첫 번째 부분 문제는 $fastSum(\frac{n}{2})$로 나타낼 수 있지만, 두 번째 부분 문제는 그렇지 않다.

문제를 재귀적으로 풀기 위해서는 각 부분 문제를 '1부터 n까지의 합' 꼴로 표현할 수 있어야 하는데, 위의 분할에서 두 번째 조각은 'a부터 b까지의 합' 형태를 가지고 있다.
따라서, 다음과 같이 두 번째 부분 문제를 $fastSum(x)$를 포함하는 형태로 바꿔야 한다.

(아래부터 이해 못함)

시간 복잡도 분석

fastSum()이 수행하는 데 걸리는 시간은 내부에 반복문이 없기 때문에,
순전히 함수가 호출되는 횟수에 비례한다.
호출될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.

$fastSum(1011_2)=fastSum(1010_2)+11$
$fastSum(1010_2)=fastSum(101_2)×2+25$
$fastSum(101_2)=fastSum(100_2)+5$
$fastSum(100_2)=fastSum(10_2)×2+4$
$fastSum(10_2)=fastSum(1_2)×2+1$
$fastSum(1_2)=1$

위는 fastSum(11)을 실행할 때 재귀 호출의 입력이 어떻게 변화하는지를 이진수 표현으로 보여준다.
재귀 호출을 할 때 n의 이진수 표현의 마지막 자리가 1이면 0으로 바뀌고,
마지막 자리가 0이면 끝자리가 없어진다는 것을 알 수 있다.
따라서 fastSum()의 총 호출 횟수는 n의 이진수 표현의 자릿수+첫 자리를 제외하고 나타나는 1의 개수가 된다.
두 값의 상한은 모두 $lgn$이므로 이 알고리즘의 실행 시간은 $O(lgn)$이다.

행렬의 거듭제곱

$n×n$ 크기의 행렬 $A$가 주어질 때, $A$의 거듭제곱 $A^m$은 $A$를 연속해서 m번 곱한 것이다.
해열르이 곱셈에는 $O(n^3)$의 시간이 들기 때문에 곧이곧대로 $m-1$번의 곱셈을 통해 $A^m$을 구하려면 모두 $O(n^3m)$번의 연산이 필요하다.

분할 정복을 이용해 눈깜짝할 새에 이 값을 구해보자.

$A^m=A^{m/2}×A^{m/2}$

위는 $A^m$을 구하는데 필요한 $m$개의 조각을 절반으로 나눈 것이다.
구현해보자.

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

나누어 떨어지지 않을 때의 분할과 시간 복잡도

$m$이 홀수일 때, $A^m=A×A^{m-1}$로 나누지 않고, 좀더 절반에 가깝게 나누는 게 좋지 않을까라는 생각을 할 수도 있다.
그러나 이 문제에서 이 방식의 분할은 오히려 알고리즘을 더 느리게 만든다.
이런 식으로 문제를 나누면 $A^m$을 찾기 위해 계산해야 할 부분 문제의 수가 늘어난다.

절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문이다.
이런 속성을 부분 문제가 중복된다(overlapping subproblems)고 부르며, 8장에서 다루는 동적 계획법이 고안된 계기다.

예제: 병합 정렬과 퀵 정렬

병합 정렬 알고리즘

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

시간 복잡도 분석

각 단계마다 반으로 나눈 부분 문제를 재귀 호출을 ㅣㅇ용해 해결한 뒤, 이들의 결과 수열을 합쳐 전체 문제의 답을 계산한다.
정렬된 두 부분 수열을 합치는 데는 두 수열의 길이 합만큼 반복문을 수행해야 하기 때문에,
병합 정렬의 수행 시간은 이 병합 과정에 의해 지배된다.

아래 단계로 내려갈수록 부분 문제의 수는 두 배로 늘고 각 부분 문제의 크기는 반으로 줄어들기 때문에,
한 단계 내에서 모든 병합에 필요한 총 시간은 $O(n)$으로 항상 일정하다.

각 단계를 나타내는 각 가로줄에 있는 원소의 수는 항상 일정하다.
따라서 단계의 수에 n을 곱하면 병합 정렬에 필요한 전체 시간을 얻을 수 있다.
문제의 크기는 항상 거의 절반으로 나누어 지기 때문에,
필요한 단계의 수는 $O(lgn)$이다.

따라서 병합 정렬의 시간 복잡도는 $O(nlgn)$이다.

퀵 정렬 알고리즘

배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다.
이를 위해 파티션(partition)이라고 부르는 단계를 도입하는데,
이는 배열에 있는 수 중 임의의 '기준 수(pivot)'을 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다.

시간 복잡도 분석

대부분의 시간을 차지하는 것은 주어진 문제를 두 개의 부분 문제로 나누는 파티션 과정이다.
파티션에는 주어진 수열의 길이에 비례하는 시간이 걸린다.

퀵 정렬의 시간 복잡도를 분석하기 따라로운 것은 결과적으로 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없기 때문이다.

기준으로 택한 원소가 최소 원소나 최대 원소인 경우 부분 문제의 크기가 하나씩만 줄어들 수도 있다.

최악의 경우 시간 복잡도는 $O(n^2)$이 되지만 평균적으로 부분 문제가 절반에 가깝게 나눠질 때 퀵 정렬의 시간 복잡도는 병합 정렬과 같은 $O(nlgn)$이 된다.

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

큰 숫자들을 다룰 때 주로 사용한다.
이렇게 큰 숫자들은 배열을 이용해 저장해야 한다.
두 자연수의 십진수 표기가 배열에 주어진다고 할 때, 이 둘을 곱한 결과를 계산하는 가장 기본적인 방법은 초등학교 산수 시간에 배운 방법을 그대로 사용하는 것이다.