코딩 테스트 대비: 동적 프로그래밍 - 0-1 Knapsack Problem 풀이

안녕하세요, GameLabMaster입니다! 이번 코딩 테스트 대비 포스팅에서는 동적 프로그래밍(Dynamic Programming) 기법을 활용한 '0-1 Knapsack Problem'에 대해 알아보겠습니다.

 

문제

당신은 배낭 한 개와 N개의 아이템들을 가지고 있습니다. 각 아이템은 무게와 가치를 가지고 있습니다. 배낭의 최대 무게는 W이며, 배낭에 담을 수 있는 아이템들의 최대 가치를 구하는 프로그램을 작성하세요. 이때, 아이템은 0개 또는 1개만 담을 수 있습니다. (0-1 Knapsack Problem)

 

입력

• 아이템의 개수 N (1 ≤ N ≤ 100)
• 배낭의 최대 무게 W (1 ≤ W ≤ 100,000)
• N개의 아이템 정보, 각 줄에는 아이템의 무게 Wi와 가치 Vi가 주어집니다. (1 ≤ Wi, Vi ≤ 1000)

출력

• 배낭에 담을 수 있는 아이템들의 최대 가치

풀이
이 문제는 동적 프로그래밍 기법을 사용하여 해결할 수 있습니다. DP 테이블을 생성하고, 각 아이템에 대해 배낭에 담을 수 있는 경우와 담지 않는 경우를 비교하여 최대 가치를 구합니다.

 

다음은 C#으로 작성한 '0-1 Knapsack Problem' 풀이 코드입니다.

 

using System;

class Program {
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int w = int.Parse(Console.ReadLine());
        int[] weights = new int[n + 1];
        int[] values = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            string[] input = Console.ReadLine().Split(' ');
            weights[i] = int.Parse(input[0]);
            values[i] = int.Parse(input[1]);
        }

        int[,] dp = new int[n + 1, w + 1];

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

        Console.WriteLine(dp[n, w]);
    }
}

 

이 코드는 먼저 아이템의 무게와 가치를 입력받고, 동적 프로그래밍 테이블 dp를 초기화합니다. 그 다음, 각 아이템에 대해 배낭에 담을 수 있는 경우와 담지 않는 경우를 비교하여 최대 가치를 구하고 출력합니다.

 

이렇게 동적 프로그래밍 기법을 활용하여 '0-1 Knapsack Problem'을 해결할 수 있습니다. 이 기법을 익히면 다양한 동적 프로그래밍 문제를 쉽게 해결할 수 있으므로, 코딩 테스트 대비에 도움이 될 것입니다. 다음 포스팅에서는 다른 동적 프로그래밍 문제에 대해 알아보겠습니다.