Java에서 동적 계획법(Dynamic Programming)을 활용한 효율적 문제 해결

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 보다 작고 관리하기 쉬운 하위 문제로 나누어 해결한 후, 그 결과를 저장하여 재활용함으로써 전체 문제의 해결을 가속화하는 프로그래밍 기법입니다. 이 방법은 중복 계산을 최소화하여 알고리즘의 효율성을 크게 향상시킵니다. Java는 클래스와 객체를 활용해 동적 계획법 알고리즘을 구현하기에 매우 적합한 언어입니다. 본문에서는 동적 계획법의 기본 원리와 함께, 피보나치 수열과 배낭 문제(Knapsack Problem)를 예로 들어 Java에서의 동적 계획법 적용 방법을 소개합니다.

• 피보나치 수열

피보나치 수열에서 n번째 숫자는 n−1번째와 n−2번째 숫자의 합으로 구성됩니다. 간단한 재귀 호출로 구현할 수 있지만, 이는 중복 계산이 많아 비효율적입니다. 동적 계획법을 사용하면 각 숫자의 계산 결과를 저장하여 중복 계산을 방지할 수 있습니다.

 

public class Fibonacci {
    public static long fib(int n) {
        long[] f = new long[n+2]; // 1을 더해주어 n이 0과 1일 때의 상황도 처리
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

    public static void main(String[] args) {
        int n = 9; // 예제로 9번째 피보나치 수를 계산
        System.out.println(n + "번째 피보나치 수: " + fib(n));
    }
}

 

 

• 0-1 배낭 문제

0-1 배낭 문제는 주어진 무게 한도 내에서 배낭에 넣을 수 있는 물건들의 가치 합이 최대가 되도록 물건을 선택하는 문제입니다. 이 문제는 동적 계획법을 사용하여 효율적으로 해결할 수 있습니다.

public class Knapsack {

    static int knapSack(int W, int wt[], int val[], int n) {
        int i, w;
        int K[][] = new int[n+1][W+1];

        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i==0 || w==0)
                    K[i][w] = 0;
                else if (wt[i-1] <= w)
                    K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
                else
                    K[i][w] = K[i-1][w];
            }
        }

        return K[n][W];
    }

    public static void main(String args[]) {
        int val[] = new int[]{60, 100, 120};
        int wt[] = new int[]{10, 20, 30};
        int W = 50;
        int n = val.length;
        System.out.println("최대 가치 합: " + knapSack(W, wt, val, n));
    }
}

 

동적 계획법은 문제를 해결하는 과정에서 중복되는 계산을 줄이는 데 큰 장점을 가지고 있으며, Java에서는 이를 쉽게 구현할 수 있는 다양한 방법을 제공합니다. 동적 계획법을 이해하고 적절히 활용하면, 복잡한 문제도 효율적으로 해결할 수 있으며, 이는 프로그래머의 문제 해결 능력을 크게 향상시킵니다.