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

분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

분할 정복의 세 단계

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

분할 정복 문제의 특성

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

행렬의 거듭제곱

A^m = (A^(m/2)) * (A^(m/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);
	// A^m = (A^(m/2)) * (A^(m/2))
	return half * half;
}