부분 문제의 답으로부터 전체 문제의 답을 도출한다.
(1) 문제를 더 작은 문제로 분할하는 과정 (Divide)
(2) 부분 문제를 원래 문제로 병합하는 과정(merge)
(3) 더이상 답을 분할하지 않고 바로 푸는 문제 (base case)
ex) 행렬의 거듭제곱
행렬의 곱셈은 주어진 행렬의 모든 원소를 가로 세로를 곱해줘야하므로 O(n^3) 의 시간 복잡도를 가진다. 이를 분할 정복을 이용해서 풀어보자.
class SquareMatrix;
SquareMatrix identity(int n);
SquareMatrix pow(const SquareMatrix& A, int m) {
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;
}