동적 프로그래밍(Dynamic Programming) 기법

정의

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 방법의 핵심은 중복되는 계산을 피하고 결과를 저장하여 재사용함으로써 효율성을 높이는 것입니다.

특징

• 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해로 구성됩니다.
• 중복되는 부분 문제(Overlapping Subproblems): 동일한 작은 문제가 여러 번 반복되어 나타납니다.
• 메모이제이션(Memoization) 또는 태뷸레이션(Tabulation): 계산 결과를 저장하고 재사용합니다.

적용 분야

• 최단 경로 문제
• 배낭 문제
• 행렬 곱셈 순서 최적화
• 문자열 편집 거리 계산

구현 방식

• Top-down (메모이제이션): 재귀적 접근 방식을 사용하며, 계산 결과를 캐시에 저장합니다.
• Bottom-up (태뷸레이션): 반복적 접근 방식을 사용하며, 작은 문제부터 큰 문제로 해결해 나갑니다.

예시 코드

피보나치 수열의 n번째 항을 계산하는 두가지 방법

public class FibonacciDP {
    // Top-down 접근 (메모이제이션)
    public static long fibMemo(int n, long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    // Bottom-up 접근 (태뷸레이션)
    public static long fibTab(int n) {
        if (n <= 1) return n;
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 50;
        long[] memo = new long[n + 1];
        
        long startTime = System.nanoTime();
        System.out.println("Top-down result: " + fibMemo(n, memo));
        long endTime = System.nanoTime();
        System.out.println("Top-down time: " + (endTime - startTime) + " ns");

        startTime = System.nanoTime();
        System.out.println("Bottom-up result: " + fibTab(n));
        endTime = System.nanoTime();
        System.out.println("Bottom-up time: " + (endTime - startTime) + " ns");
    }
}

코드 설명

1. Top-down (메모이제이션) 방식
   • 재귀적으로 문제를 해결합니다.
   • 이미 계산된 결과는 memo 배열에 저장하여 재사용합니다.
   • 중복 계산을 피할 수 있어 효율적입니다.
2. Bottom-up (태뷸레이션) 방식
   • 반복문을 사용하여 작은 문제부터 큰 문제로 해결해 나갑니다.
   • 결과를 dp 배열에 저장합니다.
   • 모든 부분 문제를 한 번씩만 계산하므로 매우 효율적입니다.

두 방식 모두 시간 복잡도는 O(n)이며, 공간 복잡도도 O(n)입니다. 이는 단순 재귀 방식의 O(2^n) 시간 복잡도에 비해 크게 개선된 것입니다.