동적계획법 (DP - Dynamic Programming)
- 재귀적인 방식으로 보다 작은 부분 문제로 나누어 부분 문제를 풀어,
이 해를 조합하여 전체 문제의 해답에 이르는 방식
- 알고리즘의 진행에 따라 탐색해야할 범위를 동적으로 결정함으로써
탐색 범위를 한정할 수 있음
동적계획법 적용 예
1. 피보나치 수열 : 직전 두 항의 합이 다음 항이 되는 것
- 재귀함수로 구현한다면?
복잡도 : 지수함수의 형태
- 동적계획법을 적용한다면?
복잡도 : 선형함수의 형태
2. Knapsack Problem
배낭에는 15kg만 담을 수 있다
kg 합이 가장 큰 값을 가지도록 물건들을 골라 배낭에 담아라
요약
문제의 성질에 따라, 동적계획법으로 풀어냄으로써 탐색해야 하는 범위를 효과적으로 줄일 수 있음
'⚖️Algorithm' 카테고리의 다른 글
| [백준 14888] 연산자 끼워넣기 (0) | 2022.07.11 |
|---|---|
| [코딩테스트] 2-3. 깊이/너비 우선 탐색(DFS/BFS) (0) | 2022.07.08 |
| [코딩테스트] 2-1. 힙(Heap) (0) | 2022.07.08 |
| [백준 10830번] 행렬 제곱 C++ (0) | 2022.07.07 |
| [코딩테스트] 1-2. 탐욕법(Greedy Algorithm) (0) | 2022.04.25 |