[ 알고리즘 ] Dynamic Programming

동적 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법

• 중복 계산 감소 : 이미 계산한 결과를 저장하고, 필요할 때마다 재활용하여 중복된 계산을 피함
• 점화식 : 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식
• 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 함 

 

완전 탐색은 다 탐색하므로 높은 시간 복잡도를 가지므로 ‘체계적’, ‘효율적’으로 탐색하기 위해서 2가지 조건이 있어야 함

• Overlapping Subproblems (중복 하위 문제) : 중복 계산해야하는 하위 문제가 존재
• Optimal Substructure (최적 부분 구조) : 하위 문제에서 구한 최적의 답이 큰 문제의 최적의 답을 구할 수 있는 구조여야 함

 

🔹 EX) 피보나치 수열

완전 탐색 $O(2^n)$

int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• 중복된 하위 문제 존재 → 기존에 계산했던 것을 기억하면, 중복 문제 피할 수 있음

 

다이나믹 프로그래밍 $O(n)$ - Top-down 방식

Map<Integer, Integer> memo = new HashMap<>();

int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
        if (!memo.containsKey(n)) {
                memo.put(n, fibonacci(n - 1) + fibonacci(n - 2));
        }
    return memo.get(n);
}

• f(n) 부터 f(1) 로 접근하므로 top-down 방식
• 재귀(recursion)으로 구현
• memo 을 채워나가는 것 → memoization

 

다이나믹 프로그래밍 $O(n)$ - Bottom-up 방식

Map<Integer, Integer> memo = new HashMap<>();

int fibonacci(int n) {
    memo.put(1, 1);
    memo.put(2, 1);
    for (int i = 3; i <= n; i++) {
        memo.put(i, memo.get(i - 1) + memo.get(i - 2));
    }
    return memo.get(n);
}

• f(1) 부터 f(n) 로 접근하므로 bottom-up 방식
• 반복문(iteration)을 통해 구현
• memo 을 채워나가는 것 → tabulation