DP(동적 계획법)
An algorithm that solves a problem by breaking it down into simpler subproblems and storing the results to avoid redundant computations.
◼︎ DP (Dynamic Programming) 동적 계획법
특정 범위까지의 값을 구하기 위해, 그것과 다른 범위까지의 값을 이용해 효율적으로 값을 구하는 알고리즘 설계 기법이다.
“답을 재활용한다.”
앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하는 등. 구체적 알고리즘 이라기 보다, 문제 해결의 패러다임에 가깝다. 어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다.
► 최적 부분구조
‘최적 부분구조’는 큰 문제의 최적해가 그것을 구성하는 작은 문제들의 최적해로부터 구해질 수 있다는 원리를 의미한다. 이를 통해 큰 문제를 작은 문제로 나누어 풀고, 이 작은 문제들의 해를 결합하여 원래의 문제를 해결할 수 있다.
► 구현
Top Down (상향식 접근)
Top Down 방식은 큰 문제를 작은 문제로 나누어 해결하는 방식이다. 이 방식은 작은 문제를 해결한 결과를 저장하고, 이를 이용하여 큰 문제를 해결한다. 이러한 방식은 ‘메모이제이션(Memoization)’이라고도 하며, 재귀 함수를 이용하여 구현할 수 있다.
Bottom Up (하향식 접근)
Bottom Up 방식은 가장 작은 문제부터 시작하여 점점 큰 문제의 해결책을 구하는 방식이다. 이 방식은 반복문을 이용하여 구현할 수 있으며, 작은 문제를 풀면서 그 해결책을 저장하고 사용한다. 이러한 방식은 ‘DP 테이블(DP Table)’이라고도 한다.
► 피보나치 수열
피보나치 수열 연산식
1
F(N) = F(N-1) + F(N-2)
► 메모이제이션
메모이제이션은 한 번 계산한 결과를 메모리에 저장해 두고, 같은 계산을 다시 할 때 저장해둔 값을 재활용하는 최적화 기법이다.
대표적으로 피보나치 수를 구할 때 메모이제이션을 활용할 수 있다.
예를 들어
피보나치수 5를 구해야 한다면 O(2^n) 만큼의 시간 복잡도가 소요된다.
다만 메모이제이션 기법을 활용하여, 이미 계산한 숫자를 메모이제이션 배열에 저장해둔다면 시간 복잡도를 O(n)으로 줄일 수 있다.
피보나치 수열 메모이제이션 방식 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Memoization_Fibonacci {
static long[] memo;
public static long fibonacci(int n) {
if (n <= 1)
return n;
else if (memo[n] != 0)
return memo[n];
else
return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
memo = new long[101];
System.out.println(fibonacci(10));
}
}
| 단계 | 설명 |
|---|---|
| 1 | ‘memo’라는 이름의 배열은 계산된 피보나치 수열의 값을 저장 |
| 2 | n이 1 이하인지 확인. n이 1 이하라면 n을 그대로 반환 |
| 3 | 계산된 값이 메모리에 있는지 확인. ‘memo[n]’이 0이 아니라면, 이미 계산된 값이므로 그 값을 반환 |
| 4 | 아직 계산되지 않은 경우에는 피보나치 수열의 정의에 따라 ‘fibonacci(n - 1) + fibonacci(n - 2)’를 계산하고, 그 결과를 ‘memo[n]’에 저장한 후 반환 |
이렇게 하면 같은 값을 다시 계산할 필요 없이, 메모리에 저장된 값을 재활용할 수 있다.
이 값을 저장하는 이유는
예를 들어, 피보나치 수열 계산과 같은 문제를 생각해보자.
피보나치 수열의 n번째 항을 구하려면 n-1번째 항과 n-2번째 항을 더해야 한다. 이 때, n-1번째 항과 n-2번째 항을 처음부터 다시 계산하지 않고, 이전에 이미 계산한 값을 재활용하면 시간을 절약할 수 있다.
예를 들어, 피보나치 수열의 5번째 항을 계산한다고 가정해보면. 이 경우 4번째 항과 3번째 항을 더해야한다. 그런데 4번째 항을 구하기 위해선 3번째 항과 2번째 항이 필요하고, 3번째 항을 구하기 위해선 2번째 항과 1번째 항이 필요하다.
이런 식으로 중복되는 계산을 반복하게 되는데, 이런 중복을 피하기 위해 이미 계산한 항들의 값을 저장해두고 재활용하는 것이 바로 메모이제이션 기법이다.