DP(Dynamic Programming) 핥아보기

동적 프로그래밍(Dynamic Programming, DP) 알고리즘은 문제를 작은 하위 문제들로 나누어 해결한 다음, 그 결과를 결합하여 원래의 문제를 해결하는 기법입니다. DP는 주로 다음 두 가지 특징을 가진 문제에 사용됩니다:

1. 중복되는 하위 문제:
   • 동일한 하위 문제가 여러 번 반복해서 계산되는 경우.
2. 최적 부분 구조:
   • 문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있는 경우.

DP 알고리즘은 크게 두 가지 방식으로 구현됩니다:

1. 탑다운(메모이제이션, Memoization):
   • 재귀를 사용하여 문제를 푸는 방식입니다.
   • 이미 계산된 하위 문제의 결과를 저장해두고, 동일한 하위 문제가 다시 등장할 때 저장된 값을 재사용합니다.
   • 이 방식은 재귀 호출로 인해 스택 오버플로우가 발생할 수 있으므로 주의가 필요합니다.
2. 바텀업(테이블화, Tabulation):
   • 반복문을 사용하여 문제를 푸는 방식입니다.
   • 가장 작은 하위 문제부터 시작하여 차례대로 상위 문제를 해결합니다.
   • 이 방식은 스택 오버플로우 문제를 피할 수 있으며, 일반적으로 탑다운 방식보다 메모리 사용이 효율적입니다.

동적 프로그래밍의 예

피보나치 수열

피보나치 수열은 동적 프로그래밍의 대표적인 예입니다. 피보나치 수열은 다음과 같은 점화식으로 정의됩니다:
[ F(n) = F(n-1) + F(n-2) ]
여기서 ( F(0) = 0 ), ( F(1) = 1 )입니다.

탑다운 방식

public class FibonacciMemoizationWithArray {
    public static void main(String[] args) {
        int n = 10;  // 예: 10번째 피보나치 수
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;  // -1로 초기화하여 아직 계산되지 않았음을 표시
        }

        int result = fib(n, memo);
        System.out.println(result);
    }

    private static int fib(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        return memo[n];
    }
}

바텀업 방식

public class FibonacciTabulation {
    public 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) {
        FibonacciTabulation ft = new FibonacciTabulation();
        System.out.println(ft.fib(10));  // 예: 10번째 피보나치 수
    }
}

0/1 배낭 문제(Knapsack Problem)

0/1 배낭 문제도 DP로 해결할 수 있는 대표적인 문제 중 하나입니다. 주어진 물건들을 배낭에 넣을지 말지 결정하여 최대 가치를 얻는 문제입니다.

public class Knapsack {
    public int knapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        Knapsack ks = new Knapsack();
        int[] weights = {1, 2, 3, 4, 5};
        int[] values = {10, 20, 30, 40, 50};
        int W = 10;
        System.out.println(ks.knapsack(weights, values, W));  // 예: 최대 배낭 용량이 10일 때 최대 값
    }
}

동적 프로그래밍은 이처럼 복잡한 문제를 효율적으로 해결할 수 있는 강력한 알고리즘 기법입니다. 다양한 문제에 적용할 수 있으며, 중복되는 계산을 피하고 최적의 해를 찾는 데 매우 유용합니다.