다이나믹 프로그래밍이란?
DP라고도하고, 동적 계획법이라고도 한다.
하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다.
정렬같은 경우는 데이터를 나눠서 처리하기 때문에, 동일한 문제를 다시 풀지 않는다.
그러나 피보나치 수열 같은 경우 재귀적으로 풀면, 뒤의 값을 구할 수록, 앞에 계산했던 내용을 또 계산하는 반복이 일어난다.
원리
DP를 사용하려면 2가지 가정이 필요하다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 값은 큰 문제에서도 동일한 값이다.(즉, 작은 문제에서 값을 구해 배열에 저장해놓고, 큰 문제에서 그 값을 사용하는 것이다.)
즉, 문제를 작게 나누어 해결하고, 나중에 전체 값을 구하는데, 그 과정에 Memoization이 사용된다.(분할정복(재귀) + Memoization)
구현
피보나치 수열을 DP로 구현해보겠다.
#include <stdio.h>
int d[100]; // 결과를 담을 수 있는 배열(전역변수로 선언했기 때문에 0으로 초기화)
// 다이나믹 프로그래밍
int dp(int x) {
// 피노나치 수열은 맨 처음 2개의 값이 1이기 때문에 초기값 명시
if(x==1) return 1;
if(x==2) return 1;
// Memoization
if(d[x]!=0) return d[x]; // 이미 구한 값이라면 구한 값 자체를 반환
return d[x] = dp(x-1) + dp(x-2); // 처음 구한 값이라면 배열에 저장
}
int main(void) {
printf("%d\n", dp(30));
}재귀적으로 피보나치를 구현했을 때 시간복잡도는 O(2^n)이지만, DP를 사용했을 때 시간복잡도는 O(N)이다.
심화문제
DP같은 경우는 문제가 나오면, 규칙성을 찾아서 점화식을 세워야한다.
reference: https://www.youtube.com/watch?v=FmXZG7D8nS4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=21
