[알고리즘] - 동적계획법 (Dynamic programming)
다이나믹 프로그래밍 (Dynamic Programming)
- 동적 계획법 이라고도 말함
- 한 문제는 한 번만 풀도록 하는 알고리즘
- 상당수 분할 정보 기법은 동일한 문제를 다시 푼다는 단점 (피보나치 수열 예시)
ㄴ 반복적으로 불필요한 계산을 해야한다는 단점
가정
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
이미 구한 답을 잠시 기억해두는 것을 '메모이제이션(Memoization)
C언어 예시
-----------------------
#include <stdio.h>
int dp(int x) {
if(x == 1) return 1;
if(x == 2) return 1;
return dp(x - 1) + dp(x - 2);
}
int main(void) {
printf("%d", dp(50)) # 시간이 오래걸림
}
-----------------------
N번째 피보나치 수열을 구할때 연산 횟수는 2^n
dp(50) 인 경우 2^50 만큼 계산해야함. -> 오래걸린다.
해결법 - 한번 계산했던 값을 변수(저장소)에 넣기 (메모이제이션 기법)
-----------------------
#include <stdio.h>
int d[100];
int dp(int x) {
if(x == 1) return 1;
if(x == 2) return 1;
if(d[x] != 0) return d[x];
return dp(x - 1) + dp(x - 2);
}
int main(void) {
printf("%d", dp(50)) # 시간이 오래걸림
}
-----------------------
n번 만큼만 계산 해주게 됨.
dp(50)이 음의 값이 나오는 이유?
- %d 출력을 정수형으로 했기 때문에 범위에 벗어나 음의 값으로 출력이 된거임. (오버 플로우)
깔끔하게 설명해주신 동빈나 선생님 감사합니다.
출처 : https://www.youtube.com/watch?v=FmXZG7D8nS4