1. 개요
DP, Dynamic Programming(동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.
2. DP를 쓰는 이유
왜 DP를 사용할까? 일반적인 재귀(Naive REcursion)방식 또한 DP와 매우 유사하다 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있다는 것이다.
피보나치 수열 식을 보면 f(n) = f(n-1) + f(n-2) 다음과 같으므로 동일한 값을 2번씩 구하게 된다. 이것을 재귀로 구하면 O(n^2) 이지만 한번 구한 작은 문제의 결과 값을 저장해두고 사용하는 DP로 구하면 O(f(n))으로 개선 할 수 있다.
3. DP의 사용 조건
1. Overlapping Subproblems (겹치는 부분 문제)
2. OPtimal Substructure (최적 부분 구조)-
Overlapping Subproblems
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능하다. -
Optimal Substructure
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
위의 그림에서 A - X 사이의 최단 거리는 AX2이고 X - B는 BX2이다. 전체 최단 경로는 AX2 - BX2이다. 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없다.
4. DP사용하기
- DP로 풀 수 있는 문제인지 확인
- 문제의 변수 파악
- 변수 간 관계식 만들기
- 메모: 변수의 값에 따른 결과 저장 (Memoization)
- 가장 작은 문제의 상태 (초기 값)
- 구현 (Bottom-up, Top-Down)
특정 데이터 내 최대화/최소화 계산, 특정 조건 내 데이터를 세거나 확률 계산하는 경우 DP로 풀 수 있는 경우가 많다.
구현 방법
-
Bottom-up
아래에서 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
메로를 위해서 dp라는 배열을 만들었고, dp[0]가 기저 상태이고 dp[n]을 목표상태 라고 하자. Bottom-up은 dp[0]부터 시작하면서 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식
Bottom-up방식은 Memoization이 아니라 Tabulation이라 부른다.
dp[0]부터 하나 하나씩 채우는 과정을 table-filling이라 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다. -
Top-Down
이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.
피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.
이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.
public class Fibonacci{
// DP 를 사용 시 작은 문제의 결과값을 저장하는 배열
// Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음)
static int[] topDown_memo;
static int[] bottomup_table;
public static void main(String[] args){
int n = 30;
topDown_memo = new int[n+1];
bottomup_table = new int[n+1];
long startTime = System.currentTimeMillis();
System.out.println(naiveRecursion(n));
long endTime = System.currentTimeMillis();
System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime));
System.out.println();
startTime = System.currentTimeMillis();
System.out.println(topDown(n));
endTime = System.currentTimeMillis();
System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime));
System.out.println();
startTime = System.currentTimeMillis();
System.out.println(bottomUp(n));
endTime = System.currentTimeMillis();
System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime));
}
// 단순 재귀를 통해 Fibonacci를 구하는 경우
// 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
public static int naiveRecursion(int n){
if(n <= 1){
return n;
}
return naiveRecursion(n-1) + naiveRecursion(n-2);
}
// DP Top-Down을 사용해 Fibonacci를 구하는 경우
public static int topDown(int n){
// 기저 상태 도달 시, 0, 1로 초기화
if(n < 2) return topDown_memo[n] = n;
// 메모에 계산된 값이 있으면 바로 반환!
if(topDown_memo[n] > 0) return topDown_memo[n];
// 재귀를 사용하고 있음!
topDown_memo[n] = topDown(n-1) + topDown(n-2);
return topDown_memo[n];
}
// DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
public static int bottomUp(int n){
// 기저 상태의 경우 사전에 미리 저장
bottomup_table[0] = 0; bottomup_table[1] = 1;
// 반복문을 사용하고 있음!
for(int i=2; i<=n; i++){
// Table을 채워나감!
bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
}
return bottomup_table[n];
}
}
/*
결과
832040
일반 재귀 소요 시간 : 9
832040
Top-Down DP 소요 시간 : 0
832040
Bottom-Up DP 소요 시간 : 0
*/분할 정복과 차이점
Divide and Conquer(분할 정복)과 DP는 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.
분할정복: 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우
DP: 동일한 중복이 일어나는 경우
