동적 계획법 Dynamic Programming 심화 - 배낭 문제, 최장 공통 부분 수열

오늘은 동적 계획법(DP)의 심화 주제인 "배낭 문제"와 "최장 공통 부분 수열(Longest Common Subsequence, LCS)"에 대해 다루어 보겠습니다. 이 두 문제는 알고리즘 학습자라면 반드시 익혀야 하는 문제 중 하나로, 다양한 실제 문제를 해결하는 데 큰 도움이 됩니다. 예제 코드 또한 Java와 C 언어로 구현하여 제공하니 비교해보며 학습하시기 바랍니다.

배낭 문제 (Knapsack Problem)

배낭 문제는 제한된 무게를 가진 배낭에 최대한 많은 가치를 가진 물건을 담는 문제입니다. 이 문제는 다양한 변형이 있지만, 오늘은 가장 기본적인 0/1 배낭 문제(각 물건을 담을지 말지를 결정하는 문제)를 다루겠습니다.

문제 설명

N개의 물건이 있고, 각 물건 i는 무게 ( w_i )와 가치 ( v_i )를 가집니다. 우리는 최대 무게가 W인 배낭에 물건들을 넣어 최대 가치를 얻고자 합니다. 각 물건은 한 번만 넣을 수 있습니다.

동적 계획법 접근법

배낭 문제는 부분 문제(subproblem)로 나누어 해결할 수 있는 전형적인 동적 계획법 문제입니다. DP 배열을 이용하여 각 무게 제한에서의 최대 가치를 저장하며 문제를 해결합니다.

Java 구현 예제

public class Knapsack {
    public static int knapsack(int W, int[] weights, int[] values, int n) {
        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(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int W = 50;
        int n = values.length;

        System.out.println("최대 가치: " + knapsack(W, weights, values, n));
    }
}

C 언어 구현 예제

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1];

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

    return dp[n][W];
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(values) / sizeof(values[0]);

    printf("최대 가치: %d\n", knapsack(W, weights, values, n));
    return 0;
}

위 예제들은 DP 배열을 사용하여 0/1 배낭 문제를 해결하는 방식입니다. 각 물건에 대해 현재 배낭의 무게에 따라 물건을 넣을지 말지를 결정하며, 최종적으로 최대 가치를 계산합니다.

최장 공통 부분 수열 (Longest Common Subsequence, LCS)

최장 공통 부분 수열은 두 문자열이 주어졌을 때, 두 문자열에 공통으로 존재하는 가장 긴 부분 수열의 길이를 찾는 문제입니다. 부분 수열은 문자열에서 문자의 순서를 유지하면서 일부 문자를 제거하여 얻을 수 있는 문자열을 말합니다.

문제 설명

두 문자열 X와 Y가 주어졌을 때, 최장 공통 부분 수열의 길이를 구하는 문제입니다.

예를 들어, 문자열 "ABCBDAB"와 "BDCABA"의 LCS는 "BCBA" 또는 "BDAB"로, 길이는 4입니다.

동적 계획법 접근법

이 문제도 부분 문제로 나누어 해결할 수 있으며, DP 배열을 사용해 각 부분 문자열 간의 최장 공통 부분 수열의 길이를 저장하면서 문제를 해결합니다.

Java 구현 예제

public class LCS {
    public static int lcs(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String X = "ABCBDAB";
        String Y = "BDCABA";

        System.out.println("최장 공통 부분 수열의 길이: " + lcs(X, Y));
    }
}

C 언어 구현 예제

#include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int lcs(char *X, char *Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCABA";

    printf("최장 공통 부분 수열의 길이: %d\n", lcs(X, Y));
    return 0;
}

위 예제들은 두 문자열의 각 문자를 비교하여 DP 배열에 공통 부분 수열의 길이를 저장하는 방식입니다. 문자가 같으면 이전 부분 문제의 결과에 1을 더하고, 그렇지 않으면 이전의 최대값을 선택합니다.

결론

오늘은 동적 계획법의 심화 주제로 배낭 문제와 최장 공통 부분 수열 문제를 다루어 보았습니다. 두 문제 모두 DP 배열을 사용하여 부분 문제를 해결하고, 이를 통해 전체 문제를 해결하는 방식입니다. 이러한 유형의 문제는 알고리즘 문제 해결 능력을 크게 향상시켜 주므로, 꼭 여러 번 풀어보시기를 권장합니다.

배낭 문제와 LCS 문제를 통해 동적 계획법의 기본 원리와 응용을 이해하는 데 도움이 되었기를 바랍니다.