[알고리즘] 동적 계획법(DP, Dynamic Programming)

동적 계획법(DP, Dynamic Programming)

동적 계획법(DP)은 복잡한 문제를 더 작은 단위로 나누어 해결하는 알고리즘 설계 기법입니다.

주로 중복 계산을 줄이기 위해 결과를 저장하고, 이를 이용하여 계산을 반복하지 않도록 합니다.

 

DP의 기본 아이디어

1. 문제를 하위 문제로 나눈다: 큰 문제를 해결하려면 먼저 작은 하위 문제들을 해결.
2. 하위 문제의 해를 저장: 하위 문제들을 해결한 후 그 결과를 저장하여, 같은 하위 문제가 다시 발생했을 때 중복 계산 하지 않음.
3. 점화식: 문제를 해결하는 규칙을 점화식으로 표현.

 

DP 문제 유형

1. 최적화 문제: 최댓값이나 최솟값을 구하는 문제 (예: 최단 경로, 배낭 문제 등)
2. 계산 결과 저장 문제: 중복된 계산을 피하기 위해 이미 계산된 값을 재사용하는 문제 (예: 피보나치 수열, 길이가 주어진 문자열 만들기 등)

 

DP의 두 가지 유형

1. 탑다운(Top-Down): 재귀 호출을 이용하고, 이미 계산된 값을 메모이제이션(Memoization) 기법을 통해 저장하여 중복 계산을 방지합니다.
2. 바텀업(Bottom-Up): 작은 문제부터 차례대로 해결해가며 결과를 저장하고 점차적으로 큰 문제를 해결해 나갑니다.

 

예제: 피보나치 수열

피보나치 수열은 DP의 기본적인 예시로 자주 사용됩니다. 피보나치 수열의 각 항은 다음과 같이 정의됩니다.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

 

1. 탑다운(Top-Down) 방식 (메모이제이션)

import java.util.*;

public class Fibonacci {

    static Map<Integer, Integer> memo = new HashMap<>();
    
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;  // 기본 조건: F(0) = 0, F(1) = 1
        }
        
        // 이미 계산된 값이 있으면 그 값을 반환
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // 계산되지 않은 경우, 재귀적으로 계산하고 메모이제이션
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 10;  // 예를 들어 10번째 피보나치 수를 구해봄
        System.out.println(fibonacci(n));  // 결과: 55
    }
}

• 동작 방식: fibonacci(n)이 호출되면, 먼저 메모리에 값이 있는지 확인하고, 없다면 재귀적으로 계산하여 메모에 저장합니다.
• 효율성: 이 방식은 중복 계산을 방지하므로 효율적으로 동작합니다.

 

2. 바텀업(Bottom-Up) 방식

public class Fibonacci {

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        // 바텀업 방식으로 DP 테이블을 채움
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        // DP 배열을 채워나감
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;  // 예를 들어 10번째 피보나치 수를 구해봄
        System.out.println(fibonacci(n));  // 결과: 55
    }
}

• 동작 방식: dp 배열을 사용해 0부터 n까지의 값을 차례대로 구해가며 피보나치 수를 계산합니다.
• 효율성: O(n)의 시간 복잡도를 가집니다. 한 번 계산된 값은 배열에 저장되어 나중에 다시 계산할 필요가 없습니다.

 

예제 2: 배낭 문제 (0/1 Knapsack Problem)

배낭 문제는 주어진 물건들을 담을 수 있는 배낭의 용량과 각 물건의 가치, 무게가 주어졌을 때 최대 가치를 구하는 문제입니다.

• 물건의 개수: n
• 배낭의 용량: W
• 물건의 무게: weights[i]
• 물건의 가치: values[i]

무게가 {2, 3, 4, 5} 가치가 {3, 4, 5, 6}일 때 배낭의 용량이 5라고 하면 그리디 알고리즘일 때 무게 5인 물건 하나를 담을 수도 있지만 가치는 무게 2, 3인 물건을 두 개 넣었을 때 7로 다른 알고리즘을 사용하면 최적해를 찾기 어려울 수 있습니다.

 

바텀업(Bottom-Up) 방식

public class Knapsack {

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

        // DP 테이블 채우기
        for (int i = 1; i <= n; i++) {
            for (int w = 0; 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) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int W = 5;  // 배낭 용량
        int n = weights.length;  // 물건 개수

        System.out.println(knapsack(W, weights, values, n));  // 결과: 7
    }
}

• 동작 방식: 각 물건에 대해 배낭에 담을 수 있을 때와 담을 수 없을 때를 고려해 dp[i][w] 값을 채웁니다.
• 효율성: 시간 복잡도는 O(nW)입니다. 여기서 n은 물건의 개수, W는 배낭의 용량입니다.

 

0	0	0	0	0	0
0	0	3	3	3	3
0	0	3	4	4	7
0	0	3	4	5	7
0	0	3	4	5	7

 

dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])

이 식은 i번째 물건을 배낭에 넣을지 말지를 결정하는 부분입니다.

dp[i - 1][w]
-> 현재 물건을 넣지 않는 경우입니다. 즉, i번째 물건을 배낭에 넣지 않으면, 이전의 i - 1개의 물건을 배낭 용량 w로 담은 최대 가치는 그대로 dp[i - 1][w]입니다

dp[i - 1][w - weights[i - 1]] + values[i - 1]
-> 현재 물건을 넣는 경우입니다.
현재 물건을 배낭에 넣으려면, 배낭의 용량 w에서 이 물건의 무게 weights[i - 1]를 뺀 용량이 남아야 합니다.

즉, 현재 물건을 넣고 나면 남은 용량은 w - weights[i - 1]가 됩니다.
이 남은 용량에서 i - 1개의 물건을 넣을 수 있는 최대 가치는 dp[i - 1][w - weights[i - 1]]입니다.
그 후 현재 물건을 배낭에 넣으면, 그 물건의 가치를 더해줘야 하므로 values[i - 1]을 더합니다.


i=2, w=5일 때를 봅니다.

dp[2][5] = Math.max(dp[1][5], (dp[1][2] + values[1]))
= max(3, 3+4)
= 7

점화식에 이렇게 대입할 수 있습니다.
남은 것들도 똑같이 점화식에 대입한 후에 표에서 찾아볼 수 있습니다.


참고 
https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C-Knapsack-Problem

 

 

연습문제

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

문제 설명
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.
펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다.
또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.

정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

제한 사항
1 ≤ sequence의 길이 ≤ 500,000
-100,000 ≤ sequence의 원소 ≤ 100,000
sequence의 원소는 정수입니다.

입출력 예
sequence result
[2, 3, -6, 1, 3, -1, 2, 4] 10

입출력 예 설명
주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

 

바텀업 방식으로 접근하며.

1, -1, 1, -1.. 을 곱한 수, 즉 양수와 음수를 번갈아 가며 더한 값이 가장 큰 것을 return 합니다.

 

문제풀이

class Solution {
    public long solution(int[] sequence) {
		long answer = 0;
		int len = sequence.length;
		
        long dp[][] = new long[len][2];
		
		dp[0][0] = sequence[0];
		dp[0][1] = -sequence[0];
		
		for (int i=1; i<len; i++) {
			dp[i][0] = Math.max(dp[i-1][1], 0) + sequence[i];
			dp[i][1] = Math.max(dp[i-1][0], 0) - sequence[i];
		}
		
		for (long[] row : dp) {
			answer = Math.max(answer, Math.max(row[0], row[1]));
		}
		
		return answer;
		
    }
}