7.1 도입

분할정복이 일반적인 재귀 호출과 다른점

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

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

</aside>

세 가지의 구성 요소

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

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

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

<aside> 📌 문제를 분할하는 과정 , 분할한 문제를 합치는 과정 , 매우 작은 문제로 구성되어있다.

</aside>

두 가지의 특징

두가지 특성문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야합니다

부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야합니다 → 많은 경우 같은 작업을 더 빠르게 처리합니다.

<aside> 📌 문제를 둘 이상의 부분 문제로 나누는 방법, 부문 문제를 조합해서 원래 문제의 답을 계산하는 방법이 존재해야한다.

</aside>

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

$\begin{aligned} fastSum() &= 1 + 2 + ... + n\\\\ &=\left(1 + 2 + ... + \frac{n}{2}\right) + \left(\left(\frac{n}{2} + 1\right)+ ... + n\right) \end{aligned}$

문제를 제귀적으로 풀기 위해서는 각 부분 문제를 '1부터 n 까지의 합' 꼴로 표현해야합니다.

첫 번째 부분 문제는 fastSum(n/2)로 나타낼수있지만, 두 번째 부분 문제는 그렇지 못합니다.