동적 계획법 DP, Dynamic Programming
DP(Dynamic Programming)은 하나의 문제 덩어리를 작은 하위 문제들로 나눈 후 하위 문제의 결과들을 저장하여 반복 계산을 줄이는 알고리즘입니다.
DP는 Top-Down(하향식)과 Bottom-Up(상향식)의 두 가지 접근법으로 나뉘어집니다.
메모이제이션 Memoization
두 접근법 설명에 앞어서 DP의 핵심 구현 개념인 메모이제이션 Memoization에 대해서 알고 넘어가야합니다. 메모이제이션은 하향식 기법을 구현하고자 할 때 사용되는 개념입니다.
메모이제이션은 동일한 결과에 대한 반복 계산 횟수를 줄이기 위해서 한 번 계산했던 결과를 저장해두고, 같은 계산 문제가 호출되면 저장해놨던 메모리에서 해당 결과를 꺼내와서 재사용함으로써 계산 효율을 크게 높여주는 구현 방식입니다.
타뷸레이션 Tabulation
마찬가지로 DP의 또 다른 핵심 구현 개념으로 타뷸레이션 Tabulation이 있습니다. 타뷸레이션은 상향식 기법을 구현하고자 할 때 사용되는 개념입니다.
타뷸레이션은 동일한 결과에 대한 반복 계산 횟수를 줄이기 위해 미리 모든 값들을 계산해서 테이블(또는 배열)에 저장해두고 필요해지면 테이블에서 결과를 꺼내와서 재사용해서 계산 효율을 크게 높여주는 구현 방식입니다.
개념 설명만 보자면 두 방식간의 차이가 거의 느껴지지 않는데요.
메모이제이션과 타뷸레이션의 차이
- 메모이제이션은 결과가 필요한 경우 계산한다. (Lazy-Evaluation)
- 타뷸레이션은 필요하지 않은 값도 미리 계산해둔다. (Eagar-Evaluation)
- 메모이제이션은 메모리와 재귀 사용
- 타뷸레이션은 테이블(배열)과 반복문 사용
즉,
메모이제이션은 코드가 간결하고 필요한만큼 계산한다는 장점이 있으나 스택 오버플로우의 위험이 있고타뷸레이션은반복문과 테이블 덕분에 성능이 더 빠르고 안정적이며 스택 오버플로우의 위험이 없다는 차이점이 있습니다.따라서 문제 상황에 맞게 두 방식 중에서 하나를 고르는 것을 추천드립니다.
- 문제가 재귀적이거나 그래프 기반의 문제에서는
메모이제이션- 재귀적으로 표현하기 어려운 문제, 안정적이고 빠른 성능을 기대할 때는
타뷸레이션
DP와 피보나치 수열
피보나치 수열은 첫째 항과 둘째 항이 1이고, 그 다음 항부터는 그 앞 두 항의 합으로 구성되는 수열입니다.
1, 1, 2, 3, 5, 8, ...
셋째 항인 2는첫째 항 1과 둘째 항 1의 합으로 구성됩니다.넷째 항 3은둘째 항 1과 셋째 항 2의 합으로 구성됩니다.- 이 과정을 쭉 반복한 수열
그래서 피보나치 수열은 다음과 같은 재귀적 정의로 표현됩니다.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2) 위와 같은 재귀적 정의로 인해 가장 대표적이면서 가장 단순한 DP 문제의 예시로 많이 등장하는 것이 피보나치 수열입니다. 그래서 여기서도 하향식과 상향식의 예시를 피보나치 수열을 이용해서 설명을 해보려고 합니다.
참고로 피보나치 수열을 분석해보면 다음과 같습니다.
-
큰 문제를 작은 문제로 나눈다.
큰 문제인 피보나치 수열 구하기를 n째 항 구하기라는 작은 문제로 나눌 수 있다. -
중복 계산 과정이 포함되어있다.
넷째 항을 구하는 과정에서 셋째 항을 구하는 식의 결과가 사용된다.
Top-Down 하향식 메모이제이션
Top-Down 하향식은 위에서부터 내려간다는 의미로, 큰 문제를 해결하고자 시도하는 과정에서 작은 문제를 재귀적으로 풀이하는 방식입니다. 이 과정에서 계산된 문제의 결과는 저장(메모이제이션)해 두고 재호출시 저장된 값을 불러오는 식으로 풀이됩니다.
하향식 메모이제이션 개념을 적용해서 피보나치 수열을 구현하면 다음과 같습니다.
public class FibonacciTopDown {
static int[] memo; //계산된 값을 저장할 memo 배열
public static int fibonacci(int n) {
if (n <= 1) {
return n; //첫째 항은 1
}
if (memo[n] != 0) {
return memo[n]; // 이미 계산된 값이면 재사용
}
//n번 항에 계산 결과 저장
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
public static void main(String[] args) {
memo = new int[n + 1]; //memo 배열 초기화 필요
}
}
n=2의 경우 재귀에 의해memo[2] = 1 + 0;가 되어 첫째 항과 둘째 항이 1이어야한다는 피보나치 수열의 기본 정의에 부합합니다.
계산 결과(수열)를 저장할 memo배열을 선언하고 재귀를 통해 피보나치 수열 구하는 메소드를 재귀 호출합니다.
이때 memo 배열에 저장된 값이 0이라면 계산된 적이 없는 수이기 때문에 새로 계산한 뒤 결과를 저장하고 0이 아닌 수가 저장되어 있다면 계산된 적이 있기 때문에 배열에서 값을 꺼내서 씁니다.
Bottom-Up 상향식 타뷸레이션
Bottom-Up은 아래서부터 올라간다는 의미로, 먼저 큰 문제를 작은 문제로 쪼갠뒤 쪼갠 작은 문제부터 해결해나가서 큰 문제를 풀어내는 방식입니다. 이 방식에서는 모든 경우를 계산해 놓고 문제에 맞는 해답을 반환합니다.
상향식 타뷸레이션 개념을 적용해서 피보나치 수열을 구현하면 다음과 같습니다.
public class FibonacciBottomUp {
public static int fibonacci(int n) {
if (n <= 1) {
return n; //첫째 항은 1. 계산전에 반환(최적화)
}
int[] dp = new int[n + 1]; //모든 계산 결과를 저장할 테이블 배열
dp[0] = 0; //0번 항은 없으니까 그냥 0
dp[1] = 1; //첫째 항은 1
//2번째 항부터 n번째 항까지 모든 결과를 계산하고 저장
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}추가 상향식 최적화
피보나치 수열의 정의에서 n번째 항은 (n - 2)번째 항 + (n - 1)번째 항으로 계산됩니다. 즉 n번째 항을 찾는다면 (n - 2), (n - 1)번째 항만을 기억하고 있으면 찾을 수 있게됩니다.
따라서 이 경우에는 저장할 테이블 대신 변수 두 개만을 사용해서 공간 최적화를 할 수 있습니다.
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int prev = 0;
int curr = 1;
for (int i = 2; i <= n; i++) {
int temp = curr;
curr = prev + curr;
prev = temp;
}
return curr;
}이렇게 DP 다이나믹 프로그래밍에 대해서 알아보았습니다. 사실 문제를 봤을 때 최소, 최대, 최적, 모든 경우의 수와 같은 문구 or 뉘앙스가 존재한다면 DP를 쓴다라고 생각하시면 됩니다.
실제로는 문제를 읽었을 때 DP를 쓰면 되겠다는 엄청 금방 떠오르는데, DP를 사용하기 위한 테이블이나 재귀 함수의 구현이 DP 문제를 어렵게 만드는 원인이기 때문에 DP 문제가 나오면 머리 한쪽이 아파지게 됩니다...
