동적계획법 (Dynamic Programming; DP) (with. 백준 1912)

Notion - 동적계획법 (Dynamic Programming; DP)

 

이번에는 DP에 대해 정리하고, 문제를 기준으로 이해해보자!

 

https://www.acmicpc.net/problem/1912 - 연속 합 / Silver 2

 

위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.

10
10 -4 3 1 5 6 -35 12 21 -1

동적계획법, DP?

동적계획법, 알고리즘을 풀 때 흔히 언급되는 DP는 큰 문제를 작은 문제들로 나누어 푸는 방법이다.

각 하위 문제들을 해결하고 저장하여 같은 하위 문제가 나왔을 때 이를 이용한다.

쉽게 말해서 문제를 작게 나누고 해결한 값을 저장해서 활용한다는 것이다.

 

위 예제를 통해 먼저 살펴보자.

위 예제는 최대 부분 수열의 합을 구하는 문제로 연속된 숫자의 합이 가장 클 때를 선택해야 한다.

 

dp 배열을 사용하여 숫자의 합을 구해나갈 때, 현재의 최적 값이 이전의 최적 값으로 부터 구해낼 수 있기 때문이다.

연속된 값을 찾기 위해 처음부터 더하면서 비교하다 보면 아래와 같은 식을 얻을 수 있다.

dp[n] = Math.max(dp[n-1] + array[n], array[n]);

이를 점화식이라고 부르며, DP 문제에서는 이를 찾는 것이 가장 큰 핵심이다.

점화식을 찾아냈으니 이제 두 가지 구현 방법을 소개할 차례다.

 

DP 문제는 두 가지 방법으로 해결해 나갈 수 있다.

• Memoization / Top-Down (재귀)
• Tabulation / Bottom-Up (반복문)

기본적으로 DP를 풀기 위해서는 초기 값 설정이 필요하다.

dp[0] = array[0]; // 초기 값 세팅
MAX = array[0];

적절한 초기 값 설정을 통해 이후의 값을 구해나갈 수 있다.

 

구현 - Memoization / Top-Down (재귀)

private static int dynamic(int index) {
    if (dp[index] == null) {
        dp[index] = Math.max(dynamic(index-1) + array[index], array[index]); // 점화식 적용
        MAX = Math.max(MAX, dp[index]); // 최댓값 갱신
    }

    return dp[index];
}

먼저, Top-Down 방식은 재귀를 이용한다.

array 배열의 마지막 인덱스 부터 시작하여 재귀를 통해 구하게 된다.

위 dynamic 메서드에서도 dp[0]의 경우를 설정해주었기에, 이후의 값을 차례대로 구해나가게 된다.

자세한 내용은 위 그림을 보는게 이해하기 편할 것이다.

 

구현 - Tabulation / Bottom-Up (반복문)

for (int i = 1; i < N; i++) {
        dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]); // 점화식 적용
        // 최댓값 갱신
        max = Math.max(max, dp[i]);
}

Bottom-Up 방식은 반복문을 이용한다.

이번에도 설정 된 초기 값으로 부터 이후 값을 차례대로 구해나가면 된다.

초기 값 이후 부터의 반복문을 시작하여 최댓값을 갱신한다.

 

정리 & 추천 문제

동적계획법의 핵심은 세 가지만 기억하면 된다.

• 하나의 문제를 작은 하위 문제로 나누어 해결해야 함 ⇒ 점화식을 구해야 함
• 이전 계산 결과를 저장하여 동일한 계산을 반복하지 않아야 함 ⇒ 메모이제이션 이용
• 하위 문제의 최적 해를 통해 문제의 최적 해가 구성될 수 있는 구조 ⇒ 타뷸레이션이 가능해야 함

점화식을 구한 뒤 메모이제이션으로 풀어나갈 지, 타뷸레이션으로 풀어나갈 지 선택하면 된다.

이번에도 DP를 연습하기 좋은 문제들을 추천할테니 풀어보면서 연습하면 도움이 될 거라고 생각한다.

 

https://www.acmicpc.net/problem/2775 - 부녀회장이 될 테야 / Bronze 1

https://www.acmicpc.net/problem/9461 - 파도반 수열 / Silver 3

https://www.acmicpc.net/problem/1149 - RGB 거리 / Silver 1

https://www.acmicpc.net/problem/1010 - 다리 놓기 / Silver 5

전체 코드

package BaekJoon.Silver.Pr1912;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Pr1912 {

    private static int N, MAX;
    private static int[] array;
    private static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        array = new int[N];
        dp = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0 ; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = array[0]; // 초기 값 세팅
        MAX = array[0];

        dynamic(N-1);

        /***
         *         for (int i = 1; i < N; i++) { // Bottom - Up 방식
         *             dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]); // 점화식 적용
         *             max = Math.max(max, dp[i]); // 최댓값 갱신
         *      }
         */

        System.out.println(MAX);
    }

    private static int dynamic(int index) {
        if (dp[index] == null) {
            dp[index] = Math.max(dynamic(index-1) + array[index], array[index]); // 점화식 적용
            MAX = Math.max(MAX, dp[index]); // 최댓값 갱신
        }

        return dp[index];
    }
}

참고

아래 분의 블로그를 보면서 DP 문제 풀이에 대한 감을 꽤 찾을 수 있었다.

위 문제들을 풀어보다가 막힌다면 아래 블로그에 찾아보는 걸 추천한다.

 

[백준] 1912번 : 연속합 - JAVA [자바]

[백준] 1912번 : 연속합 - JAVA [자바]