다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)

동적 계획법을 듣기전에 재귀와 메모이제이션에 대한 이해가 먼저 필요하다.

메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이 있는데 대표적인 방법에 동적 계획법(Dynamic Programming)이 있다. 다이나믹 프로그래밍 방식은 TopDown and BottomUp 두 가지가 있으며 메모이제이션 기법을 자주 사용한다.

Memoization : 메모리를 더 많이 사용하여 시간 복잡도를 줄이는 방법

다이나믹 프로그래밍으로 해결할 수있는 대표적인 예시가 피보나치 수열이다. 재귀에서 배웠듯이 재귀를 사용하려면 점화식을 작성해보는 것이 좋다. 피보나치 수열에 대한 점화식은 다음과 같다.

$$ n > 2 ? f(n) = f(n-2) + f(n-1) : 1 $$

피보나치 수열 같은 경우는 n 의 값이 커질 때마다 그래프의 노드가 기하급수적으로 증가하기 때문에 단순 재귀로 구현하면 안된다라는 것을 위 링크에서 느꼈을 것이다. 이러한 문제에 다이나믹 프로그래밍을 적용하면 효율적으로 해결할 수 있다.

다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다.

Top-down 방식

Top-down 방식은 큰 문제를 해결하기 위해 작은 문제를 호출한다고하여 붙여진 이름이다. Top-down 방식의 풀이는 재귀와 메모이제이션을 이용한 방법으로 푸는데, 일반적으로 다이나믹 프로그래밍 문제는 반복문을 이용하여 구하는 것이 더 성능에 좋다고 한다.

Bottom-Up 방식

Bottom-Up 방식은 작은 문제부터 차근차근 답을 도출한다고하여 붙여진 이름이다.

public class Main {

    // 입력 데이터의 갯수 n 은 10 이라 가정, 0 번째 인덱스는 사용안함
    public static long[] dp = new long[11];

    public static void main(String[] args) {
        // n 이 1 or 2일때의 값은 1
        dp[1] = 1;
        dp[2] = 1;

        // Bottom-Up 방식
        for (int i = 3; i <= 10; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
    }
}

다이나믹 프로그래밍의 전형적인 형태는 Bottom-Up 방식이다. Bottom-Up 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 Top-down 방식에 국한되어 사용되는 표현이다.

DP 테이블

DP 테이블은 결과 저장용 리스트를 의미한다. 백준 1로 만들기를 예시로 들어 설명하겠다.

• 문제
  • 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
  • X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • X가 2로 나누어 떨어지면, 2로 나눈다.
  • 1을 뺀다.
  • 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력.

해당 문제가 다이나믹 프로그래밍으로 해결해야하는 문제라고 판단이 되면, DP 테이블을 뽑아내는 기준은 간단하다. 문제에서 출력하고자 하는 부분을 보면된다. 즉, 문제에서 원하는 결과가 뭔지를 생각하면 된다.

이 문제에서 원하는 결과는 연산을 사용하는 횟수의 최솟값이다. 여기서 DP 테이블은 연산을 사용하는 횟수의 최솟값(문제에서 원하는 결과)을 저장하는 리스트라고 생각하면 된다.

• 풀이 방법
  • 초기 값을 정한다.
    • 경우에 따라서 생략해도 상관 없다.
  • 점화식을 세운다.
    • 점화식을 세울때, 문제를 그래프로 표현하거나 머릿속으로 그래프를 그려보자. 만약 그래프가 안 떠오르면 피보나치수열 그래프를 떠올리자.
    • 다이나믹 프로그래밍의 핵심은 어쨋든 이전에 계산한 결과값을 재사용하는 것이다.
    • 즉, N = 15 이고 최솟값을 구하라고하면 1 부터 15 까지 반복문을 돈다 생각하자. 5를 계산할 차례이면 5는 전에 계산된 4를 재활용할 가능성이 매우 높다.
  • 코드로 구현한다.
    • 이 과정에서 초기 값 설정한 부분이 필요 없을 수 있다. 그때 초기 값을 설정하는 코드를 지우면 된다.

public class Main {

    private static int x;
    private static int[] dp;

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(dp[x]);
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        dp = new int[x + 1];
    }

    private static void solution() {
        for (int i = 2; i <= x; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
        }
    }
}

TIP

문제에서 ~최솟값, ~최댓값을 구하라고하는 다이나믹 프로그래밍 문제는 대부분 Math.min or Math.max 를 사용한다.

다이나믹 프로그래밍의 핵심은 문제를 읽고 점화식을 세울수 있냐가 관건이다. 따라서, 다이나믹 프로그래밍의 문제들은 문제를 읽으면서 손으로 직접 정리해가면서 점화식을 세우는 것을 추천한다.

아래 사진은, '이것이 코딩테스트다' 책의 '효율적인 화폐 구성' 문제에 대한 점화식을 손으로 직접 세우는 과정이다.

처음에 머리로만 문제를 정리하여 점화식을 세우려고 했을 때는 문제를 포기했었는데, 손으로 직접 써보면서 하니 별게 아닌 문제가 되었다. 알고리즘을 풀 때, 다이나믹 프로그래밍에 대한 문제가 아니더라도 손으로 문제 대한 요구사항과 풀이 아이디어를 정리해가면서 해결하면 머리로만 해결했을때보다 문제 풀이 속도 측면에서 더 낫다고 생각된다.

References

• 이것이 코딩 테스트다