동적 계획법(Dynamic Programming)
동적 프로그래밍, 다이나믹 프로그래밍 이라고도 한다.
동적 계획법이란 하나의 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이다.
동적 계획법에서 가장 중요한 개념은 메모이제이션(Memoization)과 점화식이다.
메모이제이션(Memoization) :
동일한 계산이 반복될 때, 이전에 계산한 결과를 메모리에 저장하여 동일한 계산을 반복하는 것을 피하는 방법이다. 이전에 계산한 결과를 메모리에 저장하기 때문에 중복된 계산을 할 필요가 없으므로 속도가 빠르다는 장점이 있다.
그리고 동적 계획법에서는 이 메모이제이션을 위해 점화식을 세우는 과정이 필요하다.
동적 프로그래밍하면 가장 대표적인 예시가 바로 피보나치 수열이다.
피보나치 수열은 앞의 두 항의 합이 현재 항의 값이 되는 수열을 의미한다.
0 1 1 2 3 5 8 13 21 . . .
피보나치 수열을 코드로 짜면 다음과 같이 재귀함수로 나타낼 수 있다.
현재 항이 앞의 두 항의 합이라는 동일한 패턴이 반복되기 때문이다.
public class Main {
public static void main(String[] args) throws Exception {
long result = fibo(10); // 10번째 항
System.out.println(result); // 55
}
public static long fibo(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
}
fibo(10)의 결과를 구하기 위해 fibo(9)와 fibo(8)을 호출한다.
그리고 fibo(9)의 결과를 구하기 위해 fibo(8)과 fibo(7)을 호출한다.
마찬가지로 fibo(8)의 결과를 구하기 위해 fibo(7)과 fibo(6)을 호출한다.
그런데 이 세 번의 과정에서 fibo(8)과 fibo(7)이 두 번이나 호출되는 것을 알 수 있다.
이런식으로 fibo(10)을 구하기 위해서 동일한 재귀함수를 여러 번 호출하게 되는데,
이는 동일한 계산을 반복하는 것이므로 효율성이 떨어질 수 밖에 없다.
만약 구하고자 하는 항이 10이 아니라 50번째, 100번째, 1000번째 항을 구하고자 한다면 이보다 더 많이 동일한 계산을 반복해야 할 것이다.
그렇다면 이 문제를 해결하기 위해서는 어떻게 할 수 있을까?
이 때 사용할 수 있는 방법이 동적 계획법이다.
동적 계획법은 계산한 결과를 메모리에 저장해두고, 필요할 때 재사용하는 메모이제이션 기법을 사용한다고 했다. 피보나치 수열을 예로 들면 fibo(8)과 fibo(7)을 계산한 결과를 저장해두고, 다음에 다시 fibo(8)과 fibo(7)이 필요한 상황이 보면 다시 구할 필요 없이, 저장한 결과만 꺼내서 사용하면 되는 것이다.
보통 동적 계획법에서 메모이제이션은 배열을 이용한다.
즉, 배열을 생성하여 계산한 결과를 배열에 저장해두는 방식이다.
동적 계획법을 이용한 피보나치 수열(Down-Top)
만약 최종적으로 알고 싶은 항이 n번째 항이라면, 크기가 n+1인 배열을 하나 생성한다.
n번째 항의 결과를 알려면 n번째 값을 저장하는 장소도 있어야 하므로 배열의 크기를 n이 아닌, n+1로 잡았다.
int[] dp = new int[n+1]
이제 메모이제이션을 위한 메모리 공간을 확보한 셈이다.
dp[0]에는 0번째 항인 0이 들어가고, dp[1]에는 1번째 항인 1이 들어간다.
dp[2]에는 2번째 항인 1이 들어가고, dp[3]에는 3번째 항인 2가 들어갈 것이다.
결국, dp[n]에는 n번째 항이 들어간다.
그렇다면 각각 배열의 원소에 해당하는 값을 넣기 위해서는 어떻게 해야할까?
동적 계획법에서 메모이제이션을 하기 위해서는 점화식을 세워야 한다.
피보나치 수열에서의 점화식은 fibo(n) = fibo(n-1) + fibo(n-2) 이다.
(사실, 피보나치 수열은 모두가 흔히 아는 수열이기 때문에 점화식을 떠올리기가 쉽다. 하지만 동적 계획법 문제를 풀다보면 어려운 문제의 경우 점화식을 세우는 데 많은 시간이 소요되기도 한다.)
위의 점화식을 동적 계획법에 맞게 변경하면 dp[n] = dp[n-1] + dp[n-2] 가 된다.
이제 메모이제이션을 위한 점화식까지 구했으니, 아까의 피보나치 수열 구하는 코드를 동적 계획법 방법으로 수정하면 다음과 같다.
public static void main(String[] args) throws Exception {
long[] dp = new long[11];
dp[0] = 0; // 0번째 항
dp[1] = 1; // 1번째 항
for (int n = 2; n <= 10; n++) {
dp[n] = dp[n - 1] + dp[n - 2];
}
System.out.println(dp[10]); // 55
}
처음에 dp[0] = 0, dp[1] = 1 이 들어가고, 이 두 원소를 이용하여 dp[2] = 1를 구할 수 있다.
그러면 dp[3]은 dp[2]과 dp[1]를 이용하여 dp[3] = 2를 구할 수 있고,
dp[4]는 이미 구해진 dp[3]과 dp[2]를 이용하여 3이라는 값을 얻을 수 있다.
이런식으로 반복하다보면 dp[10]는 dp[9]와 dp[8]를 이용하여 55라는 결과를 얻는다.
처음의 재귀함수를 이용한 코드와 달리, 8번째 항과 7번째 항은 dp[8]과 dp[7]에 저장되어 있으므로 배열에서 가져다 사용하기만 하면 된다. 즉, 동일한 계산을 여러 번 할 필요가 없어지므로 속도가 훨씬 빨라진다.
아래는 동적 계획법을 사용하지 않았을 때의 걸리는 시간과, 동적 계획법을 사용했을 때 걸리는 시간을 비교한 것이다.
동적 계획법을 사용하지 않은 경우 40번째 항을 구하는데도 721ms이 걸리는 데 반해,
동적 계획법을 사용하면 100000000번째 항을 구할 때도 708ms 밖에 걸리지 않는다.
동적 계획법을 사용하지 않았을 때 피보나치 수열 :
public class Main {
public static void main(String[] args) throws Exception {
long before = System.currentTimeMillis();
int N = 40;
fibo(N);
long after = System.currentTimeMillis();
long diff = after - before;
System.out.println("시간차이(ms) : " + diff);
}
public static long fibo(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
}
동적 계획법을 사용할 때 피보나치 수열 :
public static void main(String[] args) throws Exception {
long before = System.currentTimeMillis();
int N = 100000000;
long[] dp = new long[N + 1];
dp[0] = 0;
dp[1] = 1;
for (int n = 2; n <= N; n++) {
dp[n] = dp[n - 1] + dp[n - 2];
}
long after = System.currentTimeMillis();
long diff = after - before;
System.out.println("시간차이(ms) : " + diff);
}
위 속도 비교를 통해, 동적 계획법의 속도가 월등히 빠르다는 것을 확인할 수 있다.
Top-Down 방식과 Down-Top 방식
지금까지 동적 계획법이 무엇인지 피보나치 수열 예제를 통해 간단히 살펴보았다.
동적 계획법은 어떻게 문제를 해결하느냐에 따라 크게 Top-Down방식과 Down-Top방식으로 나눌 수 있다.
Top-Down 방식 : 하나의 큰 문제를 여러 개의 작은 문제로 쪼개어서 문제를 해결하는 방식
Down-Top 방식 : 여러 개의 작은 문제를 구한 후, 이들을 합쳐서 하나의 큰 문제를 해결하는 방식
방금 우리가 동적 계획법으로 구현한 피보나치 수열 예제는 Top-Down방식일까 Down-Top방식일까?
우리는 최종적으로 n번째 항에 들어갈 값이 무엇인지를 알고 싶었다.
n번째 항을 구하기 위해 먼저, 0번째 항과 1번째 항을 알아야 했고, 2번째 항과 3번째 항을 알아야 했다.
그리고 결국 n-2번째 항(dp[n-2])과 n-1번째 항(dp[n-1])을 구했고, 최종적으로 이 두개의 값을 통해 n번째 항을 구했다.
즉, 방금 전의 동적 계획법 코드는 작은 값들을 먼저 구하고 -> n번째 항을 구하는 방식이므로
Down-Top 방식에 해당한다고 볼 수 있다.
그렇다면 Top-Down방식은 무엇일까?
처음에 재귀함수 방식을 이용한 피보나치 수열 코드를 살펴봤었다. 이 코드는 동적 계획법을 사용하진 않았지만 문제를 해결하는 방향성을 따져보자면 Top-Down방식이 맞다.
n번째 항을 구하기 위해 n-1번째 항과 n-2번째 항을 구하는 재귀함수를 호출하였고,
n-1번째 항을 구하기 위해서는 n-2번째 항과 n-3번째 항을 구하는 재귀함수를 호출한다.
n번째 항이라는 큰 문제를 해결하기 위해 하나씩 쪼개가며 문제를 해결하므로 Top-Down방식이다.
동적 계획법을 이용한 피보나치 수열(Top-Down)
그러면 이번에는 Top-Down방식으로 동적 계획법을 이용하여 피보나치 수열을 구해보자.
보통 Down-Top 방식은 반복문을 통해서 구현하고 Top-Down방식은 재귀를 이용하여 구한다고 이해하면 편하다.
첫번째 코드에서 피보나치 수열의 문제점은 동일한 계산을 반복한다는 점이었다.
이는 두 가지 케이스로 나누어서 해결할 수 있다.
만약 특정 m번째 항의 결과를 이미 구한 상태라면 dp[m]에는 그 결과값이 들어있을 것이다.
따라서 dp[m]가 0이 아니라면, m번째 항을 이미 구한 것이므로 계산을 하지 않고 dp[m]을 재사용한다.
하지만 dp[m]가 0이라면, 아직 m번째 항을 모르는 상황이므로 재귀함수를 호출한다.
1. dp[m] != 0 이라면, dp[m]를 반환
2. dp[m] == 0 이라면, fibo(m-1) + fibo(m-2)를 호출
public static long fibo(int n) {
if (n == 0)
return dp[0];
if (n == 1)
return dp[1];
if (dp[n] != 0)
return dp[n];
return dp[n] = fibo(n - 1) + fibo(n - 2);
}
아직 m번째 항을 구하지 않았을 때만 재귀함수를 호출하기 때문에 위의 코드 역시, 동일한 계산을 줄임으로써 단순히 재귀함수만을 사용했을 때에 비해 실행 시간을 줄일 수 있다.