Dynamic Programming (동적 계획법) - 기본 개념 및 Recursion 을 통한 정의

보다 효율적인 알고리즘을 위해 활용할 수 있는 패턴이 다이나믹 프로그래밍입니다. 많은 분들이 아마 어려워하는 유형일 텐데요, DP 에서는 아래 사항들만 엄밀하게 따져준다면 생각보다 알고리즘 자체는 이해하기 어렵지 않습니다.

Dynamic Programming (동적 계획법) 을 통한 문제 해결

1. Subproblem Definition (부분 문제 정의)

DP 에서는 Recursion (재귀 호출) 과 마찬가지로 복잡한 큰 문제를 여러개의 작은 문제 (Subproblem) 들로 쪼개어서 생각합니다. 즉, 하나의 큰 덩어리가 아닌 어떤 입력값에 대한 매 순간마다의 작은 덩어리를 생각하는겁니다.

2. Subproblem Relation (부분 문제 연결)

Subproblem 에 대한 정의가 끝났다면, 그 다음으로는 각 Subproblem 들이 어떻게 연결되는지를 밝혀야 할 차례입니다. 각 부분들이 어떻게 정의되는지 아는 것 만으로는 큰 덩어리 자체를 알아낼 수는 없기 때문에 각 부분들이 어떻게 합쳐지는지를 구해야 하겠죠.

3. # of Subproblems (부분 문제의 갯수)

각 문제들이 어떻게 연결이 되는지를 정의했다면, 그 다음으로는 총 해결해야 하는 Subproblem 의 갯수가 몇 개인지를 알아내야 합니다. 원래 문제가 몇 덩어리로 나눠지는지를 알아야 각 Subproblem 의 복잡도에 곱연산을 통해 원래 문제에 대한 총 복잡도를 구할 수 있기 때문이죠.

4. Topological Ordering (위상 순서)

문제를 연결하고 복잡도를 밝혀냈다고 아직 끝이 나진 않습니다. 중요한건 만들어낸 알고리즘이 정확한지를 검증해야 하는거죠. 여기서 제일 많이 실수하는 부분이 바로 "각 Subproblem 들끼리 연결될 때, 적절한 순서대로 연결되어 있는가?" 입니다. 결국 일반적인 DP 문제들은 Subproblem 이 DAG (Directed Acyclic Graph) 형태로 연결되어 있는 구조라고 볼 수 있는데, 따라서 각 Vertex (정점) 로 대표되는 subproblem 들이 올바른 위상 정렬 (Topological Sorting) 이 되어있는지를 검증해야 합니다. 그렇지 않다면 잘못된 위치 (혹은 여기서는 정점을 나타내는 subproblem) 에서 문제 해결을 시작하게 되어 올바르지 않은 결과가 나올 수 있습니다. 예를 들어:

figure 2. Topological order 가 제대로 지켜지지 않은 경우

위 처럼 시작 지점은 1번 정점인데에도 불구하고 2번 부터 해결을 시작한다면 경우에 따라 중복된 연산을 하게 되어 비효율적이거나 최악의 경우에는 잘못된 결과가 나올 수 있습니다.

위상 정렬을 한 뒤 문제를 해결할 때, 크게 두 가지의 접근법이 있습니다. 바로 Memoization (Top-down) 과 Tabulation (Bottom-up) 입니다. 두 방식은 완전히 반대 방향으로 문제를 해결해나갑니다.

Top-down Approach

제일 직관적인 문제 해결법으로, Original Problem 에서부터 시작해 해당 DP 를 나타내는 DAG 에서 마지막 정점 (즉, out-degree 가 0 인 정점) 까지 순서대로 문제를 해결해 나가는 접근법입니다. 주로 재귀 호출 (Recursion) 과 Memoization 이 사용되며, 간단히 말해 현재 Subproblem 을 해결할 때 사용되는 이전 Subproblem 의 결과값이 이미 존재하는지 확인해서 있다면 저장된 값을, 없다면 이전 Subproblem 을 해결하기 위해 재귀 호출을 하는 방식으로 로직을 짤 수 있습니다.

아래는 예시 코드 입니다:

public class DynamicProgramming {
    int n;
    Map<Integer, Integer> memo;

    int getSolution(int n) {
        this.n = n;
        this.memo = new HashMap<Integer, Integer>();
    
        // Original Problem
        return dp(n);
    }

    // Subproblem
    int dp(int i) {
        // Base case
        if (i == 0) {
            return n;
        }
    
        // Memoization
        if (memo.containsKey(i)) {
            return memo.get(i);
        }
    
        // Relation
        var cost = dp(i-1) + getCost(i) - dp(i-2);
        memo.put(i, cost);
        
        return cost;
    }

    // Cost 함수
    int getCost(int i) {
        return n - i;
    }
}

위 코드에서 아래와 같은 5가지의 특징점을 찾을 수 있습니다

Subproblem 정의: dp 라는 함수가 Subproblem 을 해결하는데 사용되는 함수인걸 확인할 수 있습니다
Base case 정의: 위의 dp 함수의 재귀 호출이 무한 루프가 되지 않도록 끝나는 조건을 명시해줍니다.
Memoizaiton: 위의 예제에서는 Read 및 Write 을 할때 둘다 상수 시간 (Constant time) 의 시간 복잡도를 가지는 HashMap 을 사용한 것을 볼 수 있습니다.
Relation: Subproblem 들의 관계를 정의해 해당 문제들을 해결하나가는 것을 볼 수 있습니다.
Original Problem 해결: i 값이 n 이 될때가 원래 문제가 되므로 dp(n) 호출을 통해 원래 문제를 해결하는 것을 볼 수 있습니다.

Bottom-up Approach

5. Solve Original Problem (원래 문제 해결)

올바른 순서로 subproblem 들이 연결되어 있다는게 검증이 되었다면, 마지막으로 실제 해결하려고 하는 원래 문제 (Original Problem) 를 해결할 차례입니다. 보통의 경우 시작점이나 끝점의 subproblem 이 결국 원래 문제를 나타내게 됩니다. (그 이후부터는 위상 정렬 순으로 각 subproblem 들이 해결되기 때문에)

따라서, $ i $ 를 iteration count, $ k $ 를 호출 횟수, $ cost(x) $ 를 $ x $ 번째 iteration 에서의 cost 함수라고 할때, 1D (1차원) DP 문제들은 일반적인 재귀 함수 형태인

$$ DP(i) = k \cdot DP(i-1) + cost(i) \; (1 \geqslant i \geqslant n, \; k > 0) $$

로 나오게 되는거죠.

Learning Never Stops