divide and conquer는 구한 sub-problems을 combine.
dp는 subproblem을 re-use하는 것.
단순히 recursive하게 문제를 푸는건 그냥 recursion.
이 3개가 겹쳐서 존재할 수도 있지만, 다를 수도 있다.\
예를 들어 어떤 문제가 무수히 많은 sub-problem으로 이루어져 있다.
그 결과들을 하나로 모아서 합친다 -> divide and conquer
그 중에서 제일 좋은 Optimal solution을 선택하는거라면 -> 분할정복 아님
근데 이때 Sub-problem들이 겹치기 때문에 재활용하려고 메모이제이션 한다. -> DP임
'코딩' 카테고리의 다른 글
| Markdown copy paste(vscode July 2024 version 1.92) (0) | 2024.08.09 |
|---|---|
| 파이썬 나누기 연산자랑 몫 연산자랑 정답이 다른 이유 (0) | 2022.08.12 |
| 카데인(Kadane) 알고리즘과 동적 프로그래밍 (0) | 2022.02.26 |
| Package ‘XXX’ was installed before R 4.0.0: please re-install it (1) | 2021.09.03 |
| "fatal error LNK1120: 1개의 확인할 수 없는 외부 참조입니다." (0) | 2019.08.29 |