DynamicProgramming(DP)-알고리즘08
1. 개요
DP(동적 계획법)은 큰 문제를 작은 부분문제들로 나누어서 푸는 하나의 문제해결 패러다임이다. 작은 문제들의 결과를 저장했다가 큰 문제를 풀때 재활용한다.
2. 목적
DP를 사용하는 이유는 일반적인 재귀는 동일한 작은 문제들을 반복해서 계산하기 때문에 비효율인 계산으로 시간이 오래걸리기 때문이다.
ex) 피보나치 수열
피보나치 수열은 다음과 같다
1 1 2 3 5 8 13 21 34 55...
이를 재귀함수로 나타내면 f(n) = f(n-1) + f(n-2) 이다.
f(5)를 재귀트리로 나타내면 아래와 같다.
이때 f(3)에서 f(2)를 계산했으나 f(4)에서 f(2)를 또 구해야 한다. 이러한 이유로 계산수가 기하급수적으로 늘어나게 되는데 이런 문제점을 저장했다가 다시 사용하는 방식으로 DP가 해결해준다.
3. 조건
DP는 두가지 사용조건이 충족되면 사용할 수 있다. 다음 두가지 조건을 충족해야 한다.
- Optimal Substructure
- Overlapping Subproblems
1. Optimal Substructure(최적 부분 구조)
어떤 문제가 최적 부분 구조를 가진다는 것은 문제의 최적해가 그 안에 부분 문제의 최적해를 포함하고 있다는 것이다.
예를들어, A->B->C->D가 A에서 D로 가는 최단거리라고 하자. 이 경로가 최단거리라면 A에서 C로 가는 최단 경로는(부분 문제) A->B->C(부분문제의 최적해) 이여야 한다.
A->F->C가 A에서 C로가는 최단경로라면, A에서 D로가는 최단경로는 A->F->C->D일 것이기 때문이다.
2. Overlapping Subproblems(겹치는 부분문제)
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 위의 예시의 피보나치 수열 처럼 같은 부분문제가 중복될 시에 DP를 사용해 시간적으로 이득을 볼 수 있다.
4. Top-down and Bottom-up
DP(다이나믹 프로그래밍)은 top-down 방식과 bottom-up 두가지 방식이 있다.
Top-down 방식은 큰 문제에서 부분문제로 쪼개어 가면서 재귀호출을 통해 문제를 푸는 방식이다.
Bottom-up 방식은 부분문제를 풀어가며 점차 큰문제를 푸는 방식이다.
예시)로 피보나치수열을 DP로 풀어보자
Top-down 방식
1) 큰 문제를 부분문제로 나눈다.
- F(n-1)과 F(n-2) 로 문제를 나눈다.
2) 부분문제를 푼다.
이때 부분문제의 해를 새로 배열을 만들어서 저장해놓고 나중에 다시 쓴다.(메모이제이션이라고 부른다)
- F(n-1) 과 F(n-2)를 구한다. 이때 이미 구한 값이라면 저장한 값을 이용한다. 구해놓지 않은 값이라면 이를 배열에 저장해 놓는다.
3) 부분문제의 답을 결합해 큰 문제를 해결한다.
- F(n-1)과 F(n-2) 값을 더해 F(n)을 구한다.
int DP[1000] = {0,}; //메모이제이션 배열
int F(int n) {
if (n <= 1) { //F(1)
return n;
} else {
if (dp[n] > 0) { // 해당 문제의 답이 존재
return DP[n];
}
DP[n] = F(n-1) + F(n-2);
return DP[n];
}
}
Bottom-up 방식
부분문제들 부터 푼다. 즉 F(1), F(2) .... 순서대로 계산하여 메모이제이션 배열에 저장,사용한다.
- F(1), F(2)값을 저장해 놓는다
- F(3) 은 F(1) + F(2) 인데 이둘은 이미 저장해 놓았으므로 이를 이용한다.
- F(4) 는 F(2)+F(3)인데 이둘은 이미 저장해 놓았다!
- F(5) 는 F(3)+F(4)인데 이둘은 이미 저장해 놓았다!
- ....
int DP[1000] = {0,}; //메모이제이션 배열
int F(int n) {
DP[0] = 0;
DP[1] = 1;
int i;
for (i=2; i<=n; i++) { // 2부터 시작해서 n까지 반복
DP[i] = DP[i-1] + DP[i-2];
}
return DP[n];
}
References
https://didu-story.tistory.com/220
https://code-lab1.tistory.com/7