[알고리즘] 동적계획법 : 다이나믹 프로그래밍 DP (Dynamic programming)

 

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

 

DP는 하나의 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 알고리즘 기법이다.

 

DP에서 동적계획법, 동적프로그래밍이라는 단어는, DP 창시자가 그냥 멋있는 단어를 붙인 것이라고 한다. 따라서 크게 의미를 부여하거나 찾아볼 필요는 없다.

 

하나의 문제를 작은 문제로 나누어 해결하는 방식은 분할정복 알고리즘과 비슷하다고 생각할 수 있다. 분할정복 알고리즘의 경우는 단순히 큰 문제를 작게 나누어 해결하는 방식에 불과하지만, DP의 경우는 작은 문제를 풀고 값을 저장하여, 중복된 계산 자체를 없애버린다.

 

 

예를 들어 피보나치 수열을 보자.

피보나치 수열은 재귀함수로, f(n) = f(n-1) + f(n-2) 의 형태를 띈다. 이때 계산 되는 과정을 보면,

 

 

f(n)을 구하기 위해 f(n-1)과 f(n-2)를 연산하고,

f(n-1)을 구하기 위해서는 f(n-2)와 f(n-3)을 연산해야한다.

 

이때, f(n-2)의 경우는 중복되는 경우이지만, 일반적인 재귀함수에서는 값을 저장하지 않기 때문에 매 회차 계산을 해 주어야 한다.

 

하지만 DP에서는 이 값을 저장해두기 때문에, 위와 같은 중복된 연산을 할 필요가 없어지므로

시간 복잡도가 낮아지게 된다.

 

 

이때,  f(n) = f(n-1) + f(n-2) 과 같은 변수 사이의 관계식을 점화식 이라고 하고, 이 점화식을 해결하기 위해선 초기값인 기저 값이 선행되어야 한다. 위 피보나치 수열에서의 기저 값은 f(0) = 0, f(1) = 1 이다.

 

또한, 중복된 연산을 저장하는 과정을 구현방법에 따라, 메모이제이션 (Memoization) 혹은 테뷸레이션 (Tabulation) 이라고 하고 , 저장된 메모리를 캐시(Cache) 라고한다.

 

 

따라서, DP는 기저 값을 설정해 준 뒤 점화식을 활용하여 캐시에서 값을 꺼내가며 문제를 해결하는 알고리즘이다.

 

 

---

다이나믹 프로그래밍 DP 사용조건

1. Overlapping Subproblems ( 작은 문제의 중복 )

큰 문제를 작게 나누었을때, 작은 문제에서 중복이 발생해야 한다.

 

중복이 발생한다는 점에서 앞서 말한 캐시에 저장한 데이터(= 작은 문제의 답)로 큰 문제를 해결한다.

이 말인 즉, 점화식을 활용해야 한다는 말이다.

 

 

2.Optimal Substructure ( 최적화된 작은 문제 )

작게 나눈 문제의 결과들이 전체 문제의 최적의 답을 도출해야 한다. 같은 문제에 대하여, 작게 나눈 문제들로 해결한 문제는 전체 문제에 대하여, 항상 같은 값을 도출해야 한다.

 

 

---

다이나믹 프로그래밍 DP 구현방법

DP의 경우 계산을 큰 문제부터 할 지, 작은 문제부터 할 지에 따라 Top-Down과 Bottom-Up으로 나눌 수 있다. 두 방식 모두, 같은 결과 값을 도출하지만 구현 방식이 다르기 때문에 사람에 따라 난이도 차이를 느낄 수 있다고 한다.

 

1. Top-Down (재귀, Memoization)

큰 문제부터 시작하여 작은 문제를 재귀문을 통하여 해결하는 방식이다.

 

top-down에서는 캐싱하는 방식을 메모이제이션 (Memoization) 이라고 하는데, 이미 계산된 값이 캐시에 있으면 꺼내는 방식이다.

 

아래는 간단한 피보나치 수열의 7번째 값을 구하는 예시이다.

public class example {

    static int[] dp = new int[8];

    public static void main(String[] args) {

        System.out.println(fibonacci(7));
    }

    public static int fibonacci(int n) {
        if (n == 0) return 0; // 기저값 설정
        if (n == 1) return 1; // 기저값 설정

        if(dp[n] > 0 ) return dp[n]; // 캐시 확인
        
        dp[n] = fibonacci(n - 1) + fibonacci(n - 2);  // 재귀 호출
        return dp[n];
    }
}

 

 

 

큰 문제인 f(7)을 구하기 위해, f(6)과 f(5)의 값이 필요하다. 둘 다 저장된 값이 없기 때문에, f(6)을 먼저 호출하게 된다.

 

f(6)의 값을 이미 구했다면, Cache에서 꺼내서 활용하고, 그렇지 않으면 f(5)와 f(4)의 값이 필요하므로, f(5)를 재귀하게 된다.

 

f(5)의 값을 이미 구했다면, Cache에서 꺼내서 활용하고, 그렇지 않으면 f(4)와 f(3)의 값이 필요하므로, f(4)를 재귀하게 된다.

 

~~~

 

위의 과정처럼 반복하다보면 f(2)를 구하기 위해, 기저 값인 f(0)과 f(1)에 도착하게 된다. 이 값은 캐시에 이미 저장되어 있고, 이 값을 활용하여 f(2)의 값을 구한다.

 

f(2)의 값을 구했으므로, f(3) = f(2) + f(1) 을 캐시의 값으로 모두 구할 수 있다.

f(3)의 값을 구했으므로, f(4) = f(3) + f(1) 을 캐시의 값으로 모두 구할 수 있다.

같은 방식으로 f(5), f(6), f(7)까지 별도의 연산 없이 값을 구할 수 있다.

 

f(7) = 13

 

 

 

 

2. Bottom-Up (반복문, Tabulation)

 

작은 문제부터 큰 문제까지를 반복문을 통하여 해결하는 방식이다.

 

bottom-up 에서는 캐싱하는 방식을 테뷸레이션 (Tabulation) 이라고 하는데, 작은 값부터 캐시에 값을 채워나가는 방식이다. 테이블에 값을 채워나간다 하여 위와 같은 이름이 붙여졌다.

 

아래는 간단히 피보나치 수열의 7번째 값을 구하는 예시이다.

public class example {

    static int[] dp = new int[8];

    public static void main(String[] args) {

        System.out.println(fibonacci(7));
    }

    public static int fibonacci(int n) {
        dp[0] = 0; // 기저값 설정
        dp[1] = 1; // 기저값 설정

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 캐시 값으로 다음 값 구하기
        }

        return dp[n];
    }
}

 

 

기저 값을 제외한 가장 작은 문제인 f(2)의 값을 먼저 구한다. 현재 캐시에 저장된 값은 아래 사진과 같고, 이 값을 활용하여 다음 값을 구한다. f(2) = f(1) + f(0)

 

값을 구하면, 캐시에 저장된 값은 아래와 같고, 이 값들로 다음 f(3)의 값을 구할 수 있다.

 

위와 같은 방법을 구하고자 하는 7까지 반복문을 통하여 반복하게된다면, 아래와 같이 캐시(테이블)을 채울 수 있다.

따라서 f(7) = 13

 

 

 

무슨 차이가 있나? 언제 무엇을 써야하나?

두 방식은 모두 같은 결과를 도출하기 때문에 편한 방법으로 구현하면 된다. 하지만, 분명한 차이는 있다.

 

Top-Down 방식의 경우,

큰 문제부터 해결하기 때문에, 점화식을 이해하기 쉽다는 장점이 있다.

 

하지만, 재귀함수를 사용하여 점화식을 작성하기 때문에, 설계 과정이 오래 걸리게 되고,

재귀함수를 호출하고 이동하는 과정에서 메모리 점유가 많아진다.

 

Bottom-Up 방식의 경우,

작은 문제부터 해결하기 때문에, 설계가 비교적 간단하고,

메모리 점유가 적어진다.

 

하지만 반대로, 점화식을 보고 전체 문제의 정답이 어떻게 도출되는 지 이해하기 힘들 수 있다.

 

 

---

DP 예시 문제

간단한 문제로, 푸는 방법과 예시를 잘 정리해 놓았다.

https://olrlobt.tistory.com/30

[자바/백준 골드5] #12865 평범한 배낭

https://olrlobt.tistory.com/31

[자바/백준 골드5] #2293 동전 1

https://olrlobt.tistory.com/32

[JAVA/백준 골드5] #2294 동전 2