7장: 분할 정복 - 1 (175p ~180p)

<도입>

1. 분할 정복

• 분할 정복(Divide & Conquer)은 주어진 문제를 둘 이상이 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용하여 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 내는 것이다.
• 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.
• 분할 정복을 사용하는 알고리즘은 대게 3개의 구성 요소를 가지고 있다.
  1. 문제를 더 작은 문제로 분할하는 과정(divide)
  2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
  3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

2. 시간 복잡도 분석

• 분할 정복은 동일한 크기의 2개의 묶음으로 문제를 나누는 경우 O(lgn)의 시간이 소요된다.

3. 행렬의 거듭제곱

• n*n 크기의 행렬 A가 주어질 때 A의 거듭제곱(power) \(A^{m}\)은 A를 연속해서 m번 곱한 것이다. 행렬의 곱셈은 \(O(n^{3})\)의 시간이 들기 때문에 \(O(mn^{3})\)의 시간이 소요되므로 m이 커지면 계산할 수 없다. 이 때 분할 정복을 이용하면 빠르게 이 값을 구할 수 있다. \(A^{m} = A^{\frac{m}{2}} \times A^{\frac{m}{2}}\)인 것을 이용하면 된다.

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

• m이 홀수일 때, \(A^{7}=A \cdot A^{6}\)이 아닌 \(A^{7}=A^{3} \cdot A^{4}\)로 나누면 호출해야할 함수의 수가 많아지므로 오히려 시간이 더 오래거리게 된다. 즉 lgn번만 호출가능한 거듭제곱보다 더 느린 것이다.