동적 계획법이란?
메모리를 사용해 수행시간의 효율성 향상시키는 방식
이미 계산된 결과를 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 한다.
Top-Down 방식과 Bottom-Up 방식(전형적) 두 가지가 있다.
- Dynamic Allocation에서 dynamic(실행 도중에 해결하는 방식)과 무관한 명칭이다.
조건
Optimal Substructure (최적 부분 구조)
Overlapping Subproblem (중복되는 부분 문제)
예시
Fibonacci 수열
a₁ = 1, a₂ = 1 이고, a_n = a_n-1 + a_n-2 이라는 점화식으로 표현할 수 있다.
재귀함수를 사용해서 풀 수 있는 문제인데, 여기서 이 수열의 계산값들을 배열이나 리스트로 저장해두면 더 빠르게 해결 가능하다. -> 계산한 결과를 다시 반복하지 않음으로써 시간을 줄일 수 있다.
- 재귀로만 계산할 경우 시간복잡도: O(2ⁿ)
메모이제이션(Memoization)
- 한번 계산한 결과를 메모리 공간에 기록해두었다가, 똑같은 연산이 필요할 때 값을 가지고 옴.
- 캐싱이라고도 함.
- DP 테이블: 결과 저장용 배열/리스트
- 메모이제이션이라는 개념이 다이내믹 프로그래밍에 국한되는 방식이 아니라는 것 주의
코드
Bottom Up 방식
#include <iostream>
long long d[100];
int main(void){
// bottom up 방식, 낮은 인덱스부터 목표 인덱스까지 차례대로 더한다.
// 첫 번째, 두 번째 요소 초기화
d[1] = 1;
d[2] = 1;
// 목표 설정
int n = 50;
// 반복문을 돌려서 a3부터 a99까지 구할 수 있도록 한다.
for(int i = 3; i<n+1; i++){
d[i] = d[i-1] + d[i-2];
}
std::cout << d[n] << std::endl;
}
Top-Down
#include <iostream>
long long d[100] = {0,};
long long fibonacci(int n){
if (n==1 || n==2){
return 1;
}
// 이미 계산한 값이면
if(d[n]!=0){
return d[n];
}else{
// 아니면 피보나치 값을 구해 배열에 저장 후 그 값 반환
d[n] = fibonacci(n-1) + fibonacci(n-2);
return d[n];
}
}
int main(){
long long res = fibonacci(50);
std::cout << res << std::endl;
return 0;
}
메모이제이션을 이용하면 시간복잡도는 O(N)으로 줄어든다.
분할 정복과의 차이
분할 정복은 문제 풀이의 반복이 일어나지 않는다는 점이다. 분할 정복은 문제를 나누지만, 각 sub 문제가 중복되지 않지만, 위에서 본 다이내믹 프로그래밍에서는 sub problem 풀이를 통해 다른 sub problem을 해결할 수 있다.
'컴퓨터기본 > 알고리즘' 카테고리의 다른 글
10. Binary Search(이진 탐색) (0) | 2021.09.24 |
---|---|
9. Flood Fill (0) | 2021.09.17 |
7. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) (0) | 2021.06.14 |
6. 스택 (Stack), 큐 (Queue) (0) | 2021.06.14 |
5. 계수 정렬 (Counting Sort) (0) | 2021.06.14 |