Dynamic Progromming
DP는 먼저 작은 부분 문제들의 해들을 구하고, 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘이다.
- 메모이제이션 (중복되는 연산의 기억)
- 중복 부분 문제 구조
- 이전 최적해는 곧 최종 최적해가 될 것이다.
- 부분 문제의 해가 최적이어야 한다.
- 스마트하게 완전탐색하는 것
💡 BFS와 DFS는 상태 공간 트리를 빠짐없이 완전 탐색한다. DP는 이러한 상태 공간 트리를
스마트하게 완전 탐색하는 기법이다.
메모이제이션
컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 다만 추가적인 메모리 공간이 필요하다는 점에서 공간 복잡도가 ↑, 시간 복잡도는 ↓ 이다.
- 중복되는 연산을 기억하기 위한 장치이다.
- 상태 공간 트리의 노드 개수만큼 메모이제이션 크기를 필요로 한다.
Top-Down 방식과 Bottom-Up 방식
일반적으로 메모이제이션 기법과 상향식으로 접근할 때를 다이나믹 프로그래밍이라고 한다.
