분할정복

분할정복이란?

1. Divide

기존 문제를 작은 부분 문제들로 나눔
풀어야할 문제가 Base Case인지 Recursive Case인지 구분한다.
Base Case
: 문제가 작아 나눌 필요 없이 바로 답을 도출하는 경우
Recursive Case
: 문제가 커서 쪼개야할 경우

2. Conquer

각 부분 문제를 해결(정복)
이 과정에서 또 다시
Divide -> Conquer-> Combine 과정으로 재귀 현상이 일어날 수 있다.

3. Combine

부분 문제들의 솔루션을 통해 기존 문제를 해결

예제

1~8까지의 합을 구하기
1~4, 5~8 까지 문제로 쪼개서 각자 더한 후 다시 합친다.
1~4 까지 구하는 경우
1~2, 3~4로 나누어서 문제 풀기
1~2의 경우 1,2로 나누기 -> Base Case로 바뀐다.
3
3~4의 경우 3,4로 나누기 -> Base Case로 바뀐다.
7
1~2(3), 3~4(7) 로 나왔다.
1~4(10) 로 나왔다.
5~8 까지 구하는 경우
위와 같은 과정을 거치면 26이 나온다.
26+10=36

출처 :https://www.youtube.com/watch?v=qDEKiNzAH1U