동적 계획 (Dynamic Programming) 알고리즘

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위한 알고리즘 기법으로, 문제를 작은 하위 문제들로 나누고, 각 하위 문제의 해를 저장하여 필요할 때 다시 사용함으로써 전체 문제를 효율적으로 해결하는 방법이다. DP는 특히 중복되는 하위 문제(subproblems)를 가진 문제에서 매우 유용하다. 즉 앞에서 설명한 분할 계획을 조금 더 효율적으로 할 수 있는 것이다. 

 

동적 계획법의 핵심 개념

1. 최적 부분 구조: 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있어야 한다.
   • 예를 들어, 최단 경로 문제에서는 전체 경로의 최단 거리는 경로의 부분 문제에서도 항상 최단 거리로 구성될 수 있다.
2. 중복되는 하위 문제: 동일한 하위 문제가 여러 번 반복해서 계산되는 경우가 있어야 한다.
   • 피보나치수열에서 F(n)=F(n−1)+F(n−2) F(n) = F(n-1) + F(n-2) F(n)=F(n−1)+F(n−2)을을 구할 때, F(n−2) F(n-2) F(n−2) 값이 여러 번 필요하다. 이 값들을 저장해 두고 재사용하면 연산을 크게 줄일 수 있다.

동적 계획법의 구현 방식

동적 계획법은 보통 두 가지 방식으로 구현해.

1. 상향식 접근 (Top-Down Approach)

• 재귀 호출을 사용하면서, 각 하위 문제의 해를 계산할 때 이미 계산한 값을 Array 또는 HashMap에 저장해 두고, 필요할 때 다시 불러와서 사용한다. .즉, 작은 문제들을 해결한 후 이를 이용해 점차 더 큰 문제를 해결해 나가는 방법입니다
• 장점: 필요한 하위 문제만 계산하기 때문에 불필요한 계산을 피할 수 있다
• 단점: 깊은 재귀 호출을 많이 사용하게 되어, 스택 오버플로우가 발생할 수 있다

public class FibonacciMemoization {
    private static int[] memo;

    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];  // 이미 계산된 값이 있다면 반환
        memo[n] = fib(n - 1) + fib(n - 2);  // 계산 후 저장
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10;
        memo = new int[n + 1];
        Arrays.fill(memo, -1);  // 메모 배열 초기화
        System.out.println("Fibonacci of " + n + " is: " + fib(n));
    }
}

 

 

2. 하향식 접근 (Bottom-Up Approach)

• 작은 문제부터 차례대로 해결하여, 그 값을 테이블에 저장하면서 전체 문제의 해답을 얻는 방법이다. 재귀적으로 작은 하위 문제로 나누어 해결하는 방식이다.
• 장점: 재귀 호출을 사용하지 않기 때문에 스택 오버플로우의 위험이 없다.
• 단점: 모든 하위 문제를 미리 계산해야 하므로, 상향식 접근에 비해 불필요한 계산이 생길 수 있다.

public class FibonacciTabulation {
    public static int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[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 = 10;
        System.out.println("Fibonacci of " + n + " is: " + fib(n));
    }
}

 

동적 계획법의 예시

1. 피보나치 수열:
   • 재귀로 풀 경우 중복된 하위 문제가 많이 발생한다. 이를  동적 계획법을 통해 중복 계산을 줄일 수 있다.
2. 최단 경로 문제 (벨만-포드 알고리즘):
   • 여러 경로의 최단 거리를 구하는 문제에서, DP를 사용해 모든 경로의 최단 거리를 효율적으로 계산할 수 있다.
3. 배낭 문제(Knapsack Problem):
   • 제한된 무게에서 최대 가치를 구하는 문제로, DP를 통해 각 물건을 선택하거나 선택하지 않는 경우를 누적하며 최적의 해결책을 찾을 수 있다.
4. LCS (Longest Common Subsequence):
   • 두 문자열의 가장 긴 공통 부분 수열을 구하는 문제로, DP를 사용해 겹치는 부분 문제를 계산하고 저장하여 효율적으로 풀 수 있다.

동적 계획법의 시간 복잡도와 공간 복잡도

• 시간 복잡도: DP는 보통 O(n) 또는 O(n^2)와 같이 효율적인 시간 복잡도를 가지며, 대부분의 경우 지수 시간 복잡도에서 다항 시간 복잡도로 문제를 최적화할 수 있다.
• 공간 복잡도: 중간 결과를 저장하기 위해 메모리를 사용하기 때문에, 공간 복잡도는 저장해야 하는 하위 문제의 개수에 따라 달라진다.

 

앞선 막대 문제를 이어가려 한다.

 

 

public static int rodCutting(int[] prices, int n) {
    int[] dp = new int[n + 1];

    // 길이 1부터 n까지 최대 이익 계산
    for (int i = 1; i <= n; i++) {
        int maxProfit = 0;
        for (int j = 1; j <= i; j++) {
            //maxProfit과 prices[j -1] 과 dp [ i - j ] 계산
            //prices [j-1] 하는 이유는 배열 시작 0이기 때문에
            maxProfit = Math.max(maxProfit, prices[j - 1] + dp[i - j]);
            System.out.println("i = "+ i+"  j= "+j+"  max = " + maxProfit);
        }
        dp[i] = maxProfit;
    }
    return dp[n];
}

 

으로 앞에서 다룬 2^n의 지수적 시간 복잡도에서 n^2으로 더 효율적으로 되었다.