DP (Dynamic Programming) / 동적 계획법
- 하나의 큰 문제를 여러개의 작은 문제로 나누어 그 결과를 저장한 뒤 다시 큰 문제를 해결할 때 사용하는 패러다임.
- 특정한 알고리즘이 아닌 하나의 문제를 해결하기 위한 패러다임.
DP
는 divide and conquer
과 큰 문제를 작은 단위로 나누어 해결하는 면에서 비슷하지만 - DP
는 부분문제가 중복되며 상위 문제 해결시 재활용된다.
Divide and conquer
에서 부분문제는 서로 중복되지 않는다.
- 이미 했던 연산이 반복되는 현상을 보완하기 위해 나타났다.
- 처음 실행하는 연산은 실시한 뒤 기록해 다음에 필요할 경우 기록해 둔 값을 가져온다.
DP를 적용한 피보나치 예시
DP
를 활용한 좋은 예시로 피보나치 수열이 있다.
int fib(int &n) {
if (n<=2) return 1;
else return fib(n-1) + fib(n-2);
}
- 일반적으로 피보나치 수열을 구하는 함수를 만들때 이런식으로 재귀를 통해
n
번째 수를 구할수 있다.
- 하지만 이런식으로 한다면
fib(5)
만 구한다고 해도
- =
fib(4)
+ fib(3)
- =
fib(3)
+ fib(2)
+ fib(2)
+ fib(1)
- =
fib(2)
+ fib(1)
+ fib(2)
+ fib(2)
+ fib(1)
- 위처럼 많은 중복 연산을 필요로 한다.
- 이점을 보완하기 위해
DP
가 고안되었다.
- 이미 진행한 연산은 기록해 둔 다음 상위 문제 해결시 재활용한다.
Top down
int fiboData[100] = {0,};
int fib(int n) {
if(n<=2) return 1;
if (fib[n]==0)
fiboData[n] = fib(n-1) + fib(n-2);
return fiboData[n];
}
fibData
배열에 연산한 값들을 저장한다.
- 다음에 중복 문제가 나올때 이 배열에서 결과값을 가져와 재연산 할 필요 없이 결과 반환이 가능하다.
fib(n)
을 호출할 때 n
부터 작은수로 내려가는데 이처럼 문제 풀이가 위에서 아래로 진행되는 것을 top down
방식이라고 한다.
Bottom up
int fib(int n) {
fibodata[0] = 0;
fiboData[1] = 1;
for(int i=2;i<=n;i++) {
fiboData[i] = fiboData[i-1] + fiboData[i-2];
}
return fiboData[n];
}
bottom up
방식은 top down
방식과 반대로 문제 풀이가 아래에서 위로 진행된다.