동적계획법, Dynamic Programming (DP)
복잡한 문제를 더 작은 하위 문제로 분해하여 해결하는 알고리즘 설계 기법
중복되는 부분 문제가 발생했을 때, 한 번만 계산하고 그 결과를 저장(메모이제이션)하여 동일한 부분 문제가 다시 발생했을 때 저장된 결과를 불러와 재활용하는 것.
이런 측면에서 기억해서 풀기 라고 불리기도 함.
특징
- 중복 계산을 줄여 계산 속도를 높일 수 있음
- 경우의 수가 많은 경우에 유용
- 재귀적으로 구현
메모이제이션 (Memoization)
말 그대로 메모한다는 의미
중복되는 계산 결과를캐시에 저장해두었다가 동일한 계산이 필요할 때 저장된 값을 불러와 재활용하는 최적화 기법.
→ 재귀 호출에서 발생하는 중복 계산을 방지하여 계산 속도를 크게 향상시킬 수 있음.
DP를 적용하기 위한 조건
최적 부분 구조
- 부분 문제의 최적해를 통해 전체 문제의 최적해를 구해질 수 있어야 함
중복되는 부분 문제
- 부분 문제가 중복되어 여러 번 반복 계산되어야 함
DP 문제 해결 방식
하향식 (Top-down) 접근 - Memoization
전체 문제를 작은 부분 문제로 나누고, 부분 문제를 해결하기 위해 재귀적으로 동작
일반적으로 재귀함수로 구현
→ 필요한 부분 문제만 해결하므로 계산 시간이 절약됨
→ BUT 메모이제이션의 처리 오버헤드가 존재할 수 있음
상향식 (Bottom-up) 접근 - Tabulation
작은 부분 문제들부터 시작해 결과를 저장하고, 이를 이용해 점진적으로 전체 문제의 해를 구함
일반적으로 반복문으로 구현
→ 직관적이고 이해가 쉬움
→ 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장
DP 문제 풀기
DP 문제는 대부분 점화식을 잘 세우는 것이 중요 !
다음과 같은 순서로 풀 수 있음
- DP로 풀 수 있는 문제인지 확인
- 문제의 변수 파악
- 점화식 만들기
- 기저 값 확인
- 구현
DP의 대표적인 예시 문제인 피보나치 수열 문제를 예시로 설명해보려 함
- DP로 풀 수 있는 문제인지 확인
위에서 설명한 최적 부분 구조와 중복되는 부분 문제의 조건을 만족하는지 확인
→ 피보나치 수열은 이전 두 항의 합을 다음 항으로 정의하는 수열이므로 적용이 가능
- 문제의 변수 파악
DP는 변수에 따라 결과 값을 찾고, 그것을 저장해 재사용하기 때문에 문제 내 변수의 개수를 파악하는 것이 중요 = state를 결정
→ 피보나치 수열은 n번째 숫자를 구해야 하므로 n이 변수가 됨
- 점화식 만들기
f(n)을 구하기 위해 이전 두 항인 f(n-1)과 f(n-2)의 값이 필요하고, f(n-1)을 구하기 위해서는 f(n-2)와 f(n-3)의 값이 필요하다
이와 같이 변수들 간의 관계를 찾아 이를 식으로 나타낸 것이 점화식
→ 피보나치 수열은 f(n) = f(n-1) + f(n-2)의 점화식을 가짐
- 메모이제이션
점화식까지 세웠다면 변수 값에 따른 결과를 저장해주어야 함
이 때, 메모이제이션할 값들은 일반적으로 배열을 사용해 저장
- 기저 값 확인
이 점화식의 해결을 위해서는 기저 값(가장 작은 문제의 상태)이 필요
→ 피보나치 수열의 경우 f(0) = 0, f(1) = 1
- 구현
피보나치 수열을 앞서 다뤘던 두 가지 접근 방식인 Bottom-up, Top-down으로 구현
public class Fibonacci{
static int[] memo; // top-down에서 사용할 배열
static int[] table; // bottom-up에서 사용할 배열
// Top-down 방식
public static int topDown(int n){
if(n<2) return memo[n] = n; // 기저 값 설정 - 0과 1로 초기화
if(memo[n]>0){ // 메모이제이션(캐시) 확인
return memo[n];
}
memo[n] = topDown(n-1) + topDown(n-2); // 재귀 호출
return memo[n];
}
// Bottom-up 방식
public static int bottomUp(int n){
table[0] = 0; // 기저 값 설정
table[1] = 1; // 기저 값 설정
for(int i=2; i<=n; i++){
table[i] = table[i-1] + table[i-2]; // 테이블의 캐시 값으로 다음 값 구하기
}
return table[n];
}
}