[Algorithm] Dynamic Programming(동적 계획법)
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다.
왜 DP를 사용할까?
사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.
피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 어떻게 될까? 단순하다. return f(n) = f(n-1) + f(n-2)
그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가한다.
왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문
그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 시간복잡도를 기준으로 아래와 같이 개선이 가능하다. O(n^2) → O(f(n)) 로 개선
DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.
1) Overlapping Subproblems(겹치는 부분 문제) ->동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능
2) Optimal Substructure(최적 부분 구조) -> 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
DP사용하기
1) DP로 풀 수 있는 문제인지 확인한다.
위에서 쓴 조건들이 충족되는 문제인지를 한 번 체크
2) 문제의 변수 파악
예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다.
3) 변수 간 관계식 만들기(점화식)
예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 였다. 이는 변수의 개수, 문제의 상황마다 모두 다를 수 있다.
4) 메모하기(memoization or tabulation)
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.
5) 기저 상태 파악하기
가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다.
피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다.
6) 구현하기
1) Bottom-Up (Tabulation 방식) - 반복문 사용
- for문을 이용해서 처음값부터 다음값을 계산해 나가는 방식이다.
- 가장 작은 문제들(Bottom)부터 차례차례 답을 구한다.
long long fib(int n) {
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++)
memo[i] = memo[i - 1] + memo[i - 2];
return memo[n];
}
2) Top-Down (Memoization 방식) - 재귀 사용
- 재귀와 같은 방식으로 위(Top)에서 아래로 내려오는 방식이다.
- 함수 호출을 줄이기 위해, 메모이제이션을 사용한다.
기존 재귀 함수 사용
int fibo(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibo(n - 1) + fibo(n - 2);
}Top-Down
long long fib(long long n){
if (n == 1 || n == 2)
return 1;
if (!memo[n])
return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}