[Java] Dynamic Programming, DP에 대해 알아보자

다이나믹 프로그래밍

다이나믹 프로그래밍에서는 큰 문제를 해결하기 위해 여러 작은 문제를 해결하고, 해결한 문제의 결과를 저장해두었다가 필요할 때 계산없이 바로 사용할 수 있도록 합니다.

이때 계산된 결과(작은 문제)는 메모리 영역인 DP 테이블에 저장하게 됩니다.

다이나믹 프로그래밍을 수행하게 되면 수행 시간 효율성을 비약적으로 향상시킬 수 있고, 동적 계획법이라고도 불립니다.

일반적으로 Top-down, Bottom-up 방식으로 구현할 수 있습니다.

 

다이나믹 프로그래밍의 조건

다이나믹 프로그래밍은 문제가 다음 두 가지 조건을 만족할 때 사용할 수 있습니다.

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

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 경우

2. 중복되는 부분 문제(Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야 하는 경우

 

피보나치 수열

다이나믹 프로그래밍의 대표적인 예시인 피보나치 수열을 살펴보겠습니다.

 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

위와 같이 피보나치 수열이 있을 때 특정 번째의 피보나치 수열은 앞에 있는 두 수를 더한 값이 됩니다.

네 번째 피보나치 수열 = 세 번째 피보나치 수열 + 두 번째 피보나치 수열 → 5 = 3 + 2

 

피보나치 수열을 점화식으로 표현하면 다음과 같습니다.

피보나치 수열을 단순히 재귀함수를 이용해서 작성하게 되면 O(2^N) 지수 시간 복잡도를 가지게 됩니다. N = 30 만 되어도 약 10억 가량의 연산을 해야하죠. 

 

피보나치 수열은 다이나믹 프로그래밍의 두 가지 조건을 모두 만족합니다.

 

1. 최적 부분 구조 성립

큰 문제 f(5)를 작은 문제 f(4)와 f(3)의 합을 통해 구할 수 있습니다.

 

2. 중복되는 부분 문제 성립

다음과 같이 fibo(5)를 구할 때 fibo(2)가 여러 번 호출되는 것처럼, 작은 문제를 중복적으로 계산합니다.

 

따라서 피보나치 수열은 다이나믹 프로그래밍 DP를 사용해서 효율적인 계산이 가능합니다.

 

다이나믹 프로그래밍 구현

피보나치 수열은 DP로 구현하는 코드를 보기 전에, DP를 구현하는 방법에 대해 살펴보겠습니다.

 

1. Top-down (메모이제이션 Memoization) 방식

Top-down 방식은 재귀를 사용합니다. 가장 큰 문제부터 시작하여, 가장 작은 문제까지 호출한 뒤, 작은 문제를 해결한 값을 저장(기억Memoization)해둡니다. 이후 저장한 값을 재활용하면서 문제를 해결합니다.

 

Memoization?

• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
  • 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님

2. Bottom-up 방식

Bottom-up 방식은 반복문을 사용합니다. 가장 작은 문제부터 시작하여, 작은 문제를 해결한 값을 저장(Tabulation)하고, 이를 기반으로 다음 문제를 해결하면서 가장 큰 문제까지 해결합니다. 

 

Tabulation?

• dp[0]부터 테이블을 하나씩 채우고(table-filling), 테이블에 저장된 값을 재활용하는 방식

 

다이나믹 프로그래밍을 사용한 피보나치 수열

> Top-down

이미 계산된 결과는 상수 시간으로 return 하기 때문에 N번째 피보나치 수열을 구하는데 걸리는 시간복잡도는 O(N)이 됩니다.

public class dpEx1 {
    public static long[] dp = new long[100];

    public static long fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        if (dp[x] != 0) {
            return dp[x];
        }
        dp[x] = fibo(x - 1) + fibo(x - 2);
        return dp[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

 

 

> Bottom-up

public class dpEx2 {
    public static long[] dp = new long[100];

    public static long fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        if (dp[x] != 0) {
            return dp[x];
        }
        dp[x] = fibo(x - 1) + fibo(x - 2);
        return dp[x];
    }

    public static void main(String[] args) {
        dp[1] = 1;
        dp[2] = 1;
        int x = 50;

        for (int i = 3; i <= x; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[x]);
    }
}