어떤 문제를 풀려고 할 때 그 문제를 비슷한 형태의 작은 부분 문제들로 쪼개서 그 부분 문제들의 답을 통해서 기존의 풀려고 했던 원래 문제의 답을 도출하는 방법을 분할 정복이라 한다.
분할 정복의 3단계
1. Divide 👉 기존 문제를 작은 부분 문제들로 나눈다.
2. Conquer 👉 각 부분 문제를 해결 (정복)
이 과정에서 부분 문제들이 다시 Divide, Conquer, Combine 되기도 한다.
3. Combine 👉 부분 문제들의 답을 통해 기본 문제를 해결
💡 문제가 Base case인지 Recursive case인지 판단해야 한다.
Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않아도 바로 답을 알 수 있는 경우
Recursive case: 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우
예시
👉 1 ~ 8까지의 합 구하기
