DP란 작은 부분 문제들의 해들을 구하고, 보다 큰 부분 문제들을 해결해가며
최종해를 구하는 방법론이다.
DP를 사용하는 조건은 아래와 같다.
- 중복 부분문제 구조
작은 문제들을 해결한 최적해로 순환적으로 큰 문제를 해결할 수 있다. (점화식)
따라서 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장하여 재사용한다.- 최적 부분문제 구조
어떤 문제의 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.
예시로써 20kg 짜리 가방이 있다고 가정하자.
그 안에 무게가 5kg고 가치가 1000원인 짐을 넣어야 하는가를 결정하려 한다.
이 짐을 넣는다 가정했을 때, 남은 15kg 가방 공간에 최적으로 짐이 들어있어야 한다.
이런 경우에만 DP를 적용할 수 있다.
DP를 적용할 수 있는 대표적인 사례는 피보나치 수열이다.
fibo1은 재귀, fibo2는 DP를 사용했다.
public class FibonacciTest1 {
private static long callCnt1;
private static long callCnt2;
// n항에 대한 값을 메모, n(index) : 원소(값)
private static long[] memo;
// non-memo
private static long fibo1(int n) { // 시간복잡도 : O(2^n)
callCnt1++;
if (n <= 1) {
return n;
}
return fibo1(n - 1) + fibo1(n - 2);
}
// memo
private static long fibo2(int n) { // 시간복잡도 : O(n)
callCnt2++;
if (memo[n] == -1) {
memo[n] = fibo2(n-1) + fibo2(n-2);
}
return memo[n];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
memo = new long[n+1]; // 메모 초기화
Arrays.fill(memo, -1);
memo[0] = 0;
memo[1] = 1;
System.out.println(fibo1(n));
System.out.println(callCnt1);
System.out.println("");
System.out.println(fibo2(n));
System.out.println(callCnt2);
}
}
fibo2에선 추가적인 배열을 이용해 시간 복잡도를 줄인 걸 알 수 있다.
n = 45를 넣으면 실행 결과는 아래와 같다.
1134903170
36726238051134903170
89
fibo1, fibo2 같은 함수를 순수함수라고 한다. 순수함수의 정의는 아래와 같다.
외부의 상태에 영향을 받거나 영향을 주지 않으면서
동일한 인자에 대해 항상 똑같은 값을 리턴하는 함수
순수함수의 개념은 DP를 사용할 때 중요하게 사용된다.
DP를 적용할 수 있는 문제는 아래와 같이 사고를 전개한다.
- 문제를 부분 문제로 나눈다.
- 부분 문제의 최적해 값에 기반해 문제의 최적해 값을 재귀적으로 정의한다.
- 정의에 따라 부분 문제의 최적해 값으로 상위 부분 문제의 최적해를 구해간다.