동적 프로그래밍 (Dynamic Programming)

설명

DP(동적 계획법)를 간단히 설명하자면 원래 문제를 하위 문제들로 나누고, 중복으로 계산되는 하위 문제들을 한 번만 계산하고 계산 결과를 재활용함으로써, 원래 문제를 효율적으로 풀 수 있게 하는 것이다. 기본적으로 중복 문제를 여러 번 계산하는 것을 막기 위해 고안된 방법이고, 따라서 각 부분 문제의 답을 메모리에 저장해놓는다.
(이 때 한 번 계산한 값을 저장해두었다 재활용하는 최적화 기법을 메모리제이션이라고 한다.)

DP를 짜는 첫 단계는, 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것이다. 그 다음 메모리제이션을 적용하면 된다.(p215, Top-Down 방식에 대한 설명인 듯)

문제 유형

다음과 같은 특성을 갖는 다양한 문제를 해결할 수 있다.(leetcode)
(1) overlapping subproblems: 원래 문제의 더 작은 버전이 반복적으로 재사용된다.
(2) optimal substructure: 하위 문제에 대한 최적의 해결책을 통해 원래 문제의 최적의 해결책을 만들 수 있다.

(Greedy 는 2를 가지고 있지만 1은 가지고 있지 않고, Divide-and-conquer 는 하위 문제로 나누긴 하는데 반복적으로 재사용되진 않는다.)

하지만 문제가 위 두 가지 특성을 가졌는지 판단하는 것은 쉽지 않다. 문제가 다음의 특성을 가졌다면 DP를 고려해볼 수 있을 것이다.

DP의 가장 일반적인 사용처는최적화 문제의 해결이다.(p225) 여러 개의 가능한 답 중 가장 좋은 답을 찾아내는 문제를 의미한다. 최소화 문제와 최대화 문제를 예시로 들 수 있다. DP를 한번 고려해볼 수 있을 것이다.

무언가를 수행하는 경우의 수를 찾는 질문에서도 DP를 고려할 수 있다. 물론 항상 DP가 최선의 접근 방식이라는 것을 의미하지는 않는다. 하지만 경우의 수를 계산하는 문제는 많은 경우 재귀적인 특징을 가지고 있다.(p251)
대개 경우의 수를 세는 문제에서 답은 input의 크기에 대해 지수적으로 증가하기에(그렇지 않을 경우 완전 탐색으로 모든 답을 셀 수 있다), % 연산을 한 후의 값을 요구한다. (모듈라 연산에 관련된 식은 14.8절에서 나올 예정)

하지만 위의 특성들을 가지고 있다면 Greedy 알고리즘으로 푸는 문제일 수도 있다. Greedy 알고리즘은 DP 보다 덜 일반적이고 식별하기 더 어렵다. 그러나 Greedy 알고리즘이 존재한다면 거의 항상 DP보다 나으므로, DP로 뛰어들기 전에 Greedy 알고리즘으로 푸는 문제인지 아닌지 한번은 고려해보아야 한다.

Greedy 문제가 아닌 DP 문제라고 식별할 수 있는 특성은 바로 미래 결정이 이전 결정의 결과에 영향을 받는다는 것이다. (예를 들어, 인접한 집의 돈을 훔칠 수 없다는 조건의 House Robber 문제에서 input [2,7,9,3,1] 이 주어졌다면 두 번째 집을 턴다면 세 번째 집을 털 수 없을 것이다. Greedy 는 미래 생각 안 하고 현재의 이익을 취할 것임) 이전 결정이 미래의 결정에 영향을 미치는 예시를 생각해낼 수 있다면 Greedy 문제가 아닌 DP 문제일 것이다.

구현 방법

하위 문제들의 답을 메모해놓고, 큰 문제를 풀어나갈 때 겹치는 문제가 나타나면 메모한 값을 이용한다.

(1) Bottom-up (a.k.a. tabulation)
base case 에서부터 시작해서 iteration 으로, 작은 문제부터 차근차근 구해나간다.

F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

장점: 보통 Top-down 보다 (overhead가 적기 때문에) 빠르다.

(2) Top-down (a.k.a. memoization)
recursion 과 memoization 으로 base case 까지 찾아가는 재귀함수를 이용한다. memoization 을 이용하지 않는다면 계산 횟수가 지수적으로 커지므로, 꼭 memoization 을 활용해야 해서 중복 계산 횟수를 줄여야 한다. memoization 을 사용하고 싶을 때 보통 hashmap 이나 array 를 사용한다.

memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

장점: 보통 Bottom-up 보다 직관적이다. 하위 문제의 순서를 고려할 필요가 없기 때문이다.(?)

프레임워크

꼭 필요한 요소들 (여기서 상태란, 시나리오를 충분히 설명할 수 있는 변수 집합)

(1) 주어진 "상태"에 대한 답을 반환하는 함수 (혹은 답을 가지고 있는 자료구조) ex. dp(n)
(2) "상태" 간 전환에 대한 재귀 관계 ex. dp(i) = dp(i - 1) + dp(i - 2)
(3) (재귀가 무한히 도는 것을 방지하기 위한) base cases

Bottom-up

base case 에서 시작하여 최종 답변까지 반복. 주로 배열을 사용한다.

public int climbStairs(int n) {
	if (n == 1) return 1;
        
	// An array that represents the answer to the problem for a given state
	int[] dp = new int[n + 1]; 
	dp[1] = 1; // Base cases
	dp[2] = 2; // Base cases
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2]; // Recurrence relation
	}   
	return dp[n];
}

Top-down

메모리제이션이 없다면 (재귀 함수에서 호출하는 함수 수)^n 만큼 시간 복잡도가 늘어난다.. 메모리제이션이 없다면 DP가 아니라 일반 재귀이다. 메모리제이션을 사용하여 최적화하면 O(n)으로 문제를 해결 가능하다. 메모리제이션은 일반적으로 해시맵 또는 배열을 사용한다.

private HashMap<Integer, Integer> memo = new HashMap<>();
    
private int dp(int i) {
	if (i <= 2) return i;
	// Instead of just returning dp(i - 1) + dp(i - 2), calculate it once and then
	// store it inside a hashmap to refer to in the future
	if (!memo.containsKey(i)) {
		memo.put(i, dp(i - 1) + dp(i - 2));
	}    
	return memo.get(i);
}
    
public int climbStairs(int n) {
	return dp(n);
}

문제 예시

피보나치 수열