다이나믹 프로그래밍(DP)?
동적 계획법이라고도 한다.
- 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 이미 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식.
- 중간 계산 결과를 기록하기 위한 메모리가 필요하다.
- 이미 계산된 부분을 재활용하기 때문에 다시 계산하지 않아 속도가 빠르다.
분할 정복과 차이점?
주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.
- 작은 문제가 중복이 일어나는지의 차이가있다.
- 분할 정복은 분할된 부분 부분이 모두 독립적이고, 동일한 부분을 중복하지 않는다.
- 예시로 병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍으로 해결 가능
예제-피보나치 수열
f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타난다. 그러므로 1회 계산했을 때, 저장된 값을 재활용할 수 있게 되는 것이다.
DP 사용법
- DP로 풀 수 있는 문제인지 확인한다.
- 문제의 변수 파악
- 변수 간 관계식 만들기(점화식)
- 메모하기(memoization or tabulation)
- 기저 상태 파악하기
- 구현하기
1)DP로 풀 수 있는 문제인지 확인한다.
-
문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단해야 한다.
-
보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.
2)문제의 변수 파악
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 즉, 문제 내 변수의 개수를 알아내야 한다는 것. 이것을 영어로 "state"를 결정한다고 한다.
피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다.
3)변수 간 관계식 만들기(점화식)
코드 내에서 점화식을 만들어 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.
피보나치 수열에서의 점화식은 f(n) = f(n-1) + f(n-2) 다.
4) 메모하기(memoization or tabulation)
변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.
변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.
5) 기저 상태 파악하기
가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다.
피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다
6) 구현하기
1) Bottom-Up (Tabulation 방식) - 반복문 사용
- 상향식 접근 방법.
- 작은 하위 문제부터 풀면서 올라간다.
- 모두 계산하면서 차례대로 진행.
2) Top-Down (Memoization 방식) - 재귀 사용
- 하향식 접근 방법.
- 큰 문제에서 하위 문제를 확인해가며 진행한다.
- 계산이 필요한 순간 계산하며 진행.
일반적인 재귀호출 방식(O(n^2))
// 단순 재귀를 통해 Fibonacci를 구하는 경우
// 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
public static int naiveRecursion(int n){
if(n <= 1){
return n;
}
return naiveRecursion(n-1) + naiveRecursion(n-2);
}DP - 메모이제이션 방식 (O(n))
// DP Top-Down을 사용해 Fibonacci를 구하는 경우
public static int topDown(int n){
int[] topDown_memo = new int[n+1];
// 기저 상태 도달 시, 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 - 타뷸레이션 방식 (O(n))
// DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
public static int bottomUp(int n){
int[] bottomup_table = new int[n+1];
// 기저 상태의 경우 사전에 미리 저장
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];
}