728x90
반응형
동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다.
동적 계획법의 핵심 이론
1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 사용한다. 이를 메모이제이션 기법이라고 한다.
4. 동적 계획법은 탑-다운 방식과 바텀-업 방식으로 구현할 수 있다.
동적 계획법의 가장 대표적인 문제인 피보나치 수열의 예
D[N] = D[N-1] + D[N-2]
동적 계획법 문제 풀이 과정
- 동적 계획법으로 풀 수 있는지 확인하기
- 점화식 세우기
- 메모이제이션 원리 이해하기
- 탑-다운 방식 이해하기
- 바텀-업 방식 이해하기
반응형
'Knowledge > 알고리즘' 카테고리의 다른 글
| 세그먼트 트리 (0) | 2024.07.18 |
|---|---|
| 최소 신장 트리 알고리즘 (0) | 2024.07.15 |
| 위상 정렬 (topology sort) (0) | 2024.07.10 |
| 유니온 파인드 알고리즘 (Union-find) (1) | 2024.07.06 |
| 최단 경로 알고리즘 (0) | 2024.07.04 |