Dynamic Programming(동적 계획법)

다이나믹 프로그래밍이란?

최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

 

DP를 쓰는 이유

일반적인 재귀방식과 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다. 예를들어 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하게 된다면

return f(n) = f(n - 1) + f(n - 2)

그러나 위의 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게되고 이로인해 100번째 피보나치수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 늘어난다.

 

이러한 반복되는 문제들의 결과값을 저장해두고 재사용하게된다면 매우 효율적으로 문제를 해결할 수 있게 된다.

 

DP의 사용 조건

DP를 사용하기 위해서는 2가지 조건을 만족해야 한다.

1. Overlapping Subproblems(겹치는 부분 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

 

2. Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다.

 

A - B 까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B(부분 문제의 최적 결과)가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B(전체 문제의 최적 결과)가 정답이 된다.

 

DP 문제 해결 방식

DP 문제 해결 방식은 크게 두가지가 있습니다.

1. Bottom-Up 방식

Bottom-Up 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식입니다. 이를 위해 반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열 등에 저장합니다.

 

ex) 백준 1912번 : 연속합

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
        int max = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        max = arr[0];

        for(int i = 1; i < N; i++) {
            dp[i] = Math.max(arr[i], arr[i] + dp[i - 1]);
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);

    }
}

주어진 수 배열 중 연속된 수에 대하여 최댓값을 구하는 문제입니다.

배열에 N만큼의 숫자를 입력하여주고 연속한 숫자의 합을 구하면됩니다. 중간에 음수도 있어 DP의 Bottom-Up방식으로 풀게된다면 쉽게 풀 수 있습니다.

2. Top-Down 방식

이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식입니다.

 

ex) 백준 1463번 : 1로 만들기

import java.util.*;
import java.io.*;

public class Main {

    static Integer[] dp;

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

        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N + 1];
        dp[0] = dp[1] = 0;

        System.out.println(makeOne(N));
    }

    static int makeOne(int num) {
        if(dp[num] == null) {
            if(num % 6 == 0)
                dp[num] = Math.min(makeOne(num - 1), Math.min(makeOne(num / 3), makeOne(num / 2))) + 1;

            else if(num % 3 == 0)
                dp[num] = Math.min(makeOne(num / 3), makeOne(num - 1)) + 1;

            else if(num % 2 == 0)
                dp[num] = Math.min(makeOne(num / 2), makeOne(num - 1)) + 1;

            else
                dp[num] = makeOne(num - 1) + 1;
        }

        return dp[num];
    }
}