Divide and Conquer 문제 푸는 법

Divide and Conquer로 문제를 풀기 위해서는

문제를 더 작은 부분 문제로 나누고, 재귀적으로 부분 문제들을 해결한다.

 

1. Base case는 문제가 충분히 작아서 바로 풀 수 있는 경우

 

2. Divide and Conquer는 총 세 단계로 나뉘게 됩니다.

1. Divide: 주어진 문제를 동일한 형태의 부분 문제로 나눈다.
2. Conquer: 각 부분 문제를 해결한다.
3. Combine: 부분 문제의 답을 활용해서, 주어진 문제의 답을 얻는다.