5. 분할 정복(Divide and Conquer)
: 문제를 나눌 수 없을 때까지 하위 문제로 나누어, 각각을 해결하고 그 결과를 이용해 전체 문제의 답을 얻는 방법
상위의 해답을 구하기 위해 아래로 내려가면서 해답을 구하는 하향식 접근법 -> 재귀로 구현
- 문제를 잘게 쪼갤 때, 부분(하위) 문제는 서로 중복되지 않음* = memoization 방식 사용할 수 없음
- 하위 문제는 현재 문제와 동일한 체계
분할 정복 단계
1. Divide: 문제를 작은 하위 문제로 분할
2. Conquer: 각 하위 문제는 재귀적으로 해결
- 부분 문제가 충분히 작아져 더 이상 재귀 호출을 할 수 없을 때: base case
3. Merge: 하위 문제의 해결책을 결합해 원래 문제를 해결
분할정복과 동적계획법(Topdown방식-memoization)의 차이?
- 분할정복은 결과를 저장하거나 재활용하지 않고(문제가 중복되지 않으니까), 하위 문제를 재귀적으로 해결
- 동적 계획법(Topdown)은 Memoization을 사용해 중복 계산을 피하고, 하위 문제의 결과를 저장해 재활용
- 둘은 비슷하지만, 각 특성으로 인해 더 적합한 상황에 사용해야 함
큰 문제를 하위 문제로 나누어 부분 구조를 이뤄야하는 점은 똑같지만
- 분할 정복: 하위 문제가 중복되지 않고 독립적으로 해결될 수 있는 경우에 적합, 중복되지 않으니까 결과를 저장하거나 재활용하지 않음 (ex. 퀵/합병 정렬)
- 동적 계획법: 하위 문제가 중복되어 재활용되는 경우에 적합, 중복되니까 중복 계산을 피하기 위해 저장/재활용 함 (ex. 피보나치 수열)
점화식?
: 일반적으로 DP는 수학의 점화식으로 표현할 수 있는 문제에 적합함(모든 문제가 점화식으로 표현될 필요가 있는 아님)->점화식으로 나타낼 수 없는 종류의 문제들은 DP를 이용해 알고리즘을 설계하기 어렵다
(ex. 정렬: 점화식으로 나타낼 수 없고, 메모이제이션을 하지 않는)
