동적 프로그래밍의 이해(막대 자르기)

동적 프로그래밍은 어떻게 보면 재귀를 통해 무수히 커지는 시간 복잡도를 메모리를 소비하여 줄이는 방법이다.

이러한 동적 프로그래밍은 상향식 방법과 하향식 방법이 있다.

막대 자르기 문제

요구사항

길이 i = {1,2,3,4,5,6,7,8,9,10} length = 10

가격 p[i] = {1,5,8,9,10,17,17,20,24,30} length = 10

의 통나무 길이에 따른 가격표가 주어진다.

이때, 현재 갖고 있는 막대의 길이 n이 주어질때, 최대로 벌 수 있는 돈의 값을 구하라.

생각의 흐름

다시 말하자면, dp는 재귀를 통해 무수히 커지는 시간 복잡도를 메모리를 소비하여 줄이는 방법이다.

즉, dp 문제는

1. 하나의 최적해를 구하기 위해서는 중복되는 부분 문제(똑같은 재귀 함수)들이 필요한 부분이 나온다.

2. 현재의 문제는 여러 개의 최적해를 가진 부분 문제로 나뉜다.

이 두 가지의 조건을 만족하는 듯 하다.

예를 들어,

1. 하나의 최적해를 구하기 위해서는 중복되는 부분 문제(똑같은 재귀 함수)들이 필요한 부분이 나온다.

-p[4]를 구하기 위해서 p[3]을 구하고 p[1]을 구해 더한다.

-p[5]를 구하기 위해서 p[3]을 구하고 p[2]를 구해 더한다.

-이때, p[3]을 구하는 부분 문제(똑같은 재귀 함수)가 나온다.

-p[4]를 구할때 p[3]을 구해야 하니 p[3]의 최적해를 구했을 때, 값을 저장해두자~

2. 현재의 문제는 여러 개의 최적해를 가진 부분 문제로 나뉜다.

-p[4]를 구하기 위해서는 p[3]을 구하고 p[1]을 구해 더해야한다.

-p[4]를 구하기 위해서는 p[2]를 구하고 p[2]를 구해 더해야한다.

이런 식인 것이다.

즉, 이 막대 자르기 문제는 dp이다.

 

위의 아이디어로 문제를 접근하게 되면, 두 가지의 방법이 떠오른다.

1. 구해야 하는 p[4] 부터 p[4] = Math.max(p[4] + p[0], p[3] + p[1], p[2] + p[2], p[1] + p[3], p[0] + p[4])의 방법과

2. p[0] 부터 거슬러 올라가며, p[0] = p[0], p[1]~~~, p[2] = Math.max(p[2] + p[0], p[1] + p[1], p[0] + p[2]),~~ p[4] = ~~의 방법이다.

이 방법을 1. 하향식, 2. 상향식 이라한다.

코드이다.

1. 하향식

import java.util.Arrays;

public class RodCutting {
    // 가격 배열
    static int[] prices = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    // 메모이제이션을 위한 배열
    static int[] memo;

    // 하향식 메서드
    public static int cutRodTopDown(int n) {
        // 이미 계산된 경우 바로 반환
        if (memo[n] >= 0) return memo[n];

        int maxValue = (n == 0) ? 0 : Integer.MIN_VALUE;

        // 각 길이로 자르는 모든 경우를 탐색
        for (int i = 1; i <= n; i++) {
            maxValue = Math.max(maxValue, prices[i] + cutRodTopDown(n - i));
        }

        // 결과를 메모에 저장
        memo[n] = maxValue;
        return maxValue;
    }

    public static void main(String[] args) {
        int n = 10; // 막대의 길이
        memo = new int[n + 1];
        Arrays.fill(memo, -1); // 메모 배열 초기화
        System.out.println("최대 수익 (하향식): " + cutRodTopDown(n));
    }
}

2. 상향식

public class RodCutting {
    static int[] prices = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    // 상향식 메서드
    public static int cutRodBottomUp(int n) {
        int[] dp = new int[n + 1]; // DP 배열 초기화

        // 길이 1부터 n까지 최대 수익 계산
        for (int i = 1; i <= n; i++) {
            int maxValue = Integer.MIN_VALUE;

            // 길이 i에 대해 모든 자르는 경우 탐색
            for (int j = 1; j <= i; j++) {
                maxValue = Math.max(maxValue, prices[j] + dp[i - j]);
            }
            dp[i] = maxValue; // 최대 수익 저장
        }
        return dp[n]; // 최종 결과 반환
    }

    public static void main(String[] args) {
        int n = 10; // 막대의 길이
        System.out.println("최대 수익 (상향식): " + cutRodBottomUp(n));
    }
}

이렇게 비교해보면, 재귀의 방법을 쓰는 하향식보단 상향식이 더 편해보인다. 실제로 똑같은 점근적 수행 시간을 갖지만, 상향식이 재귀를 쓰지 않기에, 오버헤드가 작다.

 

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

동적 프로그래밍의 부분 문제들은 모두 독립적이어야 한다.

분할 정복 vs 동적 프로그래밍

-> 둘 다 재귀적 특성을 이용한다는 면에서 비슷하지만, 하위 부분 문제를 저장하는 것에서 차이가 있다. 즉, 하위 부분 문제가 재사용되는 경향이 있다면, 동적 프로그래밍이 알맞다. 반면, 재사용되지 않는 경향이 있다면, 분할 정복이 알맞다.

라는 생각을 해보았다.

 

그리디 vs 동적 프로그래밍

-> 그리디로 풀 수 있는 문제의 대다수는 동적 프로그래밍으로 풀 수 있다고 생각한다. 그리디와 동적 프로그래밍은 둘 다 최적해를 찾아가는 과정이지만, 그리디는 굳이 모든 부분 문제를 살펴보지 않아도 될 때, 사용할 수 있다.

라는 생각을 해보았다.

 

그리디 vs 동적 프로그래밍 vs 완전 탐색

-> 최적해를 찾아갈 때 사용할 수 있을만한 방법들이다. 셋 다 사용할 수 있는 문제라면, 그리디->동적 프로그래밍->완전탐색 순으로 사용할 수 있다.

라는 생각을 해보았다.