다이나믹 프로그래밍 (Dynamic Programming, DP)
: 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
위 사진과 같이 피보나치 수열을 DP를 이용해서 배열로 문제를 풀 수 있다.\
배열에 하위 값들에 대한 정보를 저장하고 있으면, 상위 문제를 풀 때 배열에 저장된 값을 이용해서 풀 수 있기 때문에 재귀보다 훨씬 수행시간이 줄어든다.
DP를 푸는 과정
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기
'알고리즘 > 공부' 카테고리의 다른 글
| [바킹독 알고리즘] 0x14강 - 투 포인터 (0) | 2024.07.04 |
|---|---|
| [바킹독 알고리즘] 0x18강 : 그래프 (0) | 2023.09.10 |
| [바킹독 알고리즘] 0x0A강:DFS in 다차원 배열 (0) | 2023.01.22 |
| [알고리즘] 이진탐색 알고리즘 (Binary Search) (0) | 2023.01.18 |
| [바킹독 알고리즘] 0x09강:BFS in 다차원 배열 (0) | 2023.01.12 |