[Algorithm/Java] DP(다이나믹 프로그래밍, 동적 계획법)

다이나믹 프로그래밍 (DP , 동적 계획법)

크고 복잡한 문제를 여러 개의 작고 간단한 문제들로 분리하여 문제를 해결하는 방법이다.

답을 찾아가는 과정에서 작은 문제들을 계산한 결과를 기록하고, 재활용하며 문제의 답을 구하는 방식이다.

 

• 중간 계산 결과를 기록하기 위한 메모리가 필요하다.
• 한번 계산한 부분을 기록해두기 때문에 다시 계산하지 않아서 속도가 빠르다.

---

DP 핵심 원리

DP를 사용하려면

• 큰 문제를 작은 문제 여러개로 나눌 수 있어야 한다.
• 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.

DP 구현 방법

• 메모이제이션(memoization) 방법 : 모든 작은 문제들을 한 번만 계산해서 DP 테이블에 저장하여, 그 값들을 재사용하는 방법
• 타뷸레이션(Tabulation) 방법 : 작은 문제부터 순차적으로 계산하며 상위로 올라가는 방법
• 탑 다운 방식 : 큰 문제에서 작은 하위 문제들을 확인해 가며 진행하는 방식이다.
• 바텀 업 방식 : 타뷸레이션 방법이 바텀 업 방식이다.

 

DP의 가장 유명하고 간단한 예제로 피보나치수열 이 있다.

피보나치 수열 : D [N] = D[N - 1] + D[N - 2]

이 문제를 DP 방식으로 해결해 보자.

---

1. DP 방식을 적용할 수 있는지 확인

6 번째 피보나치수열은 5번째 피보나치수열과 4번째 피보나치수열의 합이다.

또한, 5번째 피보나치수열은 4번째 피보나치 수열과 3번째 피보나치수열의 합이다.

즉, 피보나치 수열은 N번째 수열을 구하는 방법을, N-1번째와 N-2번째 수열을 구하는 작은 문제로 나눌 수 있고,

이 값들은 항상 같기 때문에 DP를 적용할 수 있다.

---

2. 점화식 세우기

점화식은 작은 문제들로부터 큰 문제의 답을 찾아내는 식을 일반화 했다고 생각하면 된다.

피보나치 수열의 점화식은 간단하다. 위에서 말했듯이, D [N] = D[N - 1] + D[N - 2]이다.

그러나 이보다 훨씬 복잡하고, 여러 가지 조건을 생각해야 하는 점화식들도 많다.

따라서, 전체 문제와 부분 문제 간의 연관 관계를 파악하는 훈련이 필요하다.

---

3. 문제 해결

점화식을 도출해 냈다면 DP 방식의 문제는 거의 해결한 것과 다름없다.

DP 테이블을 생성하고, 여러 가지 작은 문제들의 값들을 점화식을 바탕으로 해결해 나가면 된다.

피보나치수열의 경우 이미 알고 있는 D [1] = 1, D [2] = 1을 바탕으로 D [3]부터 원하는 값까지 점화식에 따라 반복 계산하면 될 것이다.

이 문제에서 DP를 이용했을 때 속도가 빠른 이유는 D [N]을 구하고자 할 때 필요한 D [N-1], D [N-2] 값은 이미 구해져 있기 때문에 인덱스로 접근해서 값만 찾아오면 되기 때문이다. 즉, 전에 계산했 던 같은 문제를 중복해서 계산하지 않기 때문이다.

---

메모이제이션 방법

메모이제이션은 부분 문제를 풀었을 때, 해당 결과를 DP 테이블에 저장해 놓고 다음에 조금 더 큰 문제를 해결할 때 가져다 쓰는 방법이다. 바로 위(3. 문제해결)에서 말했듯이, D [N-1], D [N-2]는 이미 계산해서 저장해 두었었고, 이를 D [N] 값을 구할 때 가져다 쓰기만 하면 되는 것이다.

 

아래 그림을 보면 D [5]를 구하고자 할 때, DP 테이블에 이미 알고 있는 값인 D [1], D [2]를 초기화하는 것으로 시작한다.

그다음은 D [3]부터 D [2], D [1]을 이용해서 구하고, D [4]는 D [3], D[2]를 이용해서 구한다. 이 때, D[3], D [2]는 이미 값을 구해서 DP 테이블에 저장해 뒀기 때문에 저장해 둔 값을 가져다 쓰기만 하면 되는 것이다.

점화식을 이용해 DP테이블에 값을 채워나가다가 마지막 D [5]까지 찾고 답을 반환하면 되는 것이다.

이렇게 하면 불필요한 반복 연산과 탐색이 줄어들어서 시간복잡도를 많이 줄일 수 있게 된다.

추가로 D [5]를 구할 때를 생각해 보자. 

D [4]와 D [3]의 값을 알아야 한다. 만약 메모이제이션 방식을 사용하지 않는다면 D[3]을 구하기 위해 D[2], D [1]을 계산해야 할 것이고, D[4]를 구하기 이해 D[3]과 D[2]를 구하기위해 계산해야 할것이다. D[4]를 구하기위한 D[3]의 값을 얻기 위해서는 또다시 D[2]와 D[1]을 더하는 연산을 해야 한다. 이러한 과정들을 DP테이블에 값을 저장해 둠으로써 생략할 수 있는 것이다.

---

피보타치 수열 문제 풀어보기

1. 탑-다운 방식

7번째 피보나치수열 값을 구하는 예제이다.

fibonacci 메서드를 재귀적으로 호출해야 하기 때문에 static으로 dpTable을 생성하고 fibonacci(7)을 실행해 보자.

dpTable을 초기화한 상태 그대로 모든 값이 0으로 둬도 되지만, 조금 더 확실하게 하기 이해 -1로 초기화를 해줬다.

public class DP_TopDown{
    static int[] DP;

    public static void main(String[] args) {
        //피보나치 수열
        int n = 7;
        DP = new int[n + 1];
        for (int i = 0; i < DP.length; i++) {
            DP[i] = -1;
        }
        System.out.println(fibonacci(n));
    }

    public static int fibonacci(int n){
        if(n <= 2){
            return 1;
        }
        if(DP[n] != -1){
            return DP[n];
        }
        DP[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return DP[n];
    }
}

해당 재귀함수의 종료 조건은 두 가지이다.

첫 번째로 n = 1, n = 2 일 때는 위에서 말한 초기값이다. 따라서 이때는 그냥 1을 반환한다.

 

두 번째는 이제 dpTable을 업데이트하는 과정이다.

DP [n]의 값이 -1이 아닐 때는 이미 DP table에 값이 있는 상태이므로 해당 값을 반환한다.

 

두 가지 조건이 전부 해당되지 않는 경우는 아직 DP table에 값이 없는 상태이므로 재귀 방식으로 DP [n]에 값을 업데이트해준다.

---

2. 바텀-업 방식

바텀 업 방식은 초기 값 DP [1] = 1, DP [2] = 1 부터 시작해서 더 큰값으로 계속 올라가는 방식이다.

이 문제는 간단하기 때문에 이 방법이 조금 더 직관적이다.

public class DP_Bottom_up {
    //타뷸레이션(바텀 업) 방식으로 풀이
    public static void main(String[] args) {
        //피보나치 수열
        int n = 7;
        System.out.println(fibonacci(n));
    }
    public static int fibonacci(int n) {
        int[] DP = new int[n < 2 ? 2 : n+1];
        DP[1] = 1;
        DP[2] = 1;

        for (int i = 3; i <= n; i++) {
            DP[i] = DP[i - 1] + DP[i - 2];
        }
        return DP[n];
    }
}

초기 값 DP[1] = 1, DP[2] = 1을 초기화한다.

이후에는 DP [3]부터 구하고자 하는 DP [n]까지 간단하게 for문을 돌며 업데이트해주면 된다.

---

두 방식 모두 유효한 방법이다. 하지만 바텀 업 방식에서의 점화식을 구하기 어려운 경우도 많고, 재귀함수를 이용하는 것이 어려운 경우도 많다. 따라서 두 방식 중에 자신이 편한 방식을 이용하면 된다.

 

추가로 탑-다운 방식의 재귀함수 방식은 재귀의 깊이가 매우 깊어질 경우 런타임오류가 발생할 수 있다. 그러나 코딩테스트 수준에서 그 정도로 깊은 재귀를 요구하는 문제는 잘 나오지 않는다고 한다.