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

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

 

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.

당연히 큰 문제를 작은 문제를 나누는 것과 다이나믹은 아무런 관련이 없다

이 용어를 처음 사용한 Richard Bellman은 그냥 '다이나믹'이 멋있어 보여서 사용했다고..ㅋ

 

다이나믹 프로그래밍으로 풀 수 있는 문제는 두가지 속성을 만족해야 한다.

 

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

큰 문제를 여러개의 부분 문제로 나누어서 풀 때 부분 문제간의 중복이 발생 가능해야 한다.

 

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

문제의 정답을 작은 문제의 정답을 통해 구할 수 있어야 한다. 예를 들어 대전에서 부산을 갈 때 최적의 루트가 대구를 거치는 거라면 서울에서 대전을 거쳐 부산을 갈 때 최적의 루트 역시 대구를 거치는 상황이어야 한다는 것이다. 즉 이를 만족하는 상황이라면 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

 

라고 적어는 놨지만 이대로는 이해가 어려우니

예로 피보나치 수열을 보자.

 

- 피보나치 수열

 

피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , 55 ... 와 같다.

즉 첫번째는 0, 두번째는 1로 정해져있고 이후의 숫자는 뒤의 두 숫자를 더한 값이 오게 되어 있는 수열이다

 

공식으로는

 

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2 (n >= 2)

 

와 같이 나타낼 수 있는데 

여기서 N은 N-1이나 N-2보다 크니까

Fn 즉 N번째 피보나치 수를 구하는 문제가 큰 문제라고 할 수 있고

N-1번째 피보나치 수와 N-2번째 피보나치 수를 구하는 Fn-1과 Fn-2는 작은 문제라고 할 수 있다

 

그런데 여기서 N-1번째 피보나치 수를 구하는 문제가 큰 문제가 된다면

N-2번째 피보나치 수와 N-3번째 피보나치 수를 구하는 문제는 작은 문제가 되는데

 

N-2번째 피보나치 수를 구하는 건

N번째 피보나치 수를 구하는 문제에서도 큰 문제를 구하기 위해 작은 문제로 쪼갰던 문제다.

 

이렇게 작은 문제간의 중복이 발생 가능한 상황.

이런 경우를 Overlapping Subproblem에 해당하는 상황이라고 할 수 있다

 

Optimal Substructure는 N번째 피보나치 수가 일정한 상황으로 확인할 수 있는데

10번째 피보나치 수를 구할때나 9번째 피보나치 수를 구할 때나 4번째 피보나치 수는 항상 같은 게

DP로 문제를 풀기 위해 필요한  '최적 부분 구조' 조건을 만족하는 문제임을  할 수 있다.

 

같은 문제는 구할 때마다 정답이 같은 이와 같은 성질이 있기 때문에 

다이나믹 프로그래밍에서 각 문제는 한번만 풀어야 한다.

따라서 정답을 한번 구현했으면 배열을 활용해 정답을 메모해 놓고 쓰는 게 좋다

 

즉 피보나치 수열을 코드로 

 

int fibonacci(int n) {
 
    if (n <= 1) {
        return n;
    }else {
        return fibonacci(n-1) + fibonacci(n-2)
    }
 
}

 

이렇게 구현하고 5를 n에 해당하는 인자로 줬다고 하면

 

재귀로 fibonacci(n-1)을 구하는 과정에서 fibonacci(4), fibonacci(3),fibonacci(2),  fibonacci(1), fibonacci(0)을 호출하고

 fibonacci(n-2)를 구하는 과정에서 또 fibonacci(3),fibonacci(2),  fibonacci(1), fibonacci(0)을 호출하는 등

수많은 중복이 발생하게 된다. 그러나 아래와 같이

 

int memo[100];
int fibonacci(int n) {
 
    if (n <= 1) {
        return n;
    }else {
        if(memo[n] > 0){
            return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
 
}

이 다이나믹 프로그래밍은 구현 방식도 두가지가 있다

 

하나는 큰 문제부터 문제를 쪼개가면서 작은 문제를 만들고 다시 합쳐가면서 원래 문제를 푸는 Top-Down 방식

다른 하나는 작은 문제를 풀고 그보다 하나 큰 큰 문제 풀고를 반복하며 쌓아 올라가는 Bottom-Up 방식이라고 하는데

 

뭔가 말이 어렵지만 재귀를 활용하면 Top-Down. 반복문을 활용하면 Bottom-Up이라고 생각하면 된다.

 

그러니까 위에서 구한 피보나치 수열은 Top-Down 방식으로 구현한 것이고

Bottom-Up 방식으로 구한 것은 아래와 같다

 

int d[100];
int fibonacci(int n) {
 
    d[0] = 0;
    d[1] = 1;
    
    for (int i=2; i<=n; i++) {
        d[i] = d[i-1] + d[i - 2];
    }
 
    return d[n];
}

 

- Top-Down vs Bottom Up

 

대부분은 뭘로 구현하든 답은 구할 수 있다. ( 둘 중 하나로만 풀 수 있는 문제도 있다는 말 )

그럼 무엇을 써야 할까? 그러나 이에 대한 답은 문제마다 다르다.

 

재귀로 풀면 스택 오버 플로가 발생할 수 있는 문제도 있고 ( 사실 그 전에 재귀가 어려울 수도 있고 )

반복문으로 풀면 너무 많이 반복해서 효율적이지 않을 경우도 있다. 

 

그러니 일단은 편한 걸로 시작해 두 방식 모두 편하게 사용할 수 있도록 훈련하는 것을 추천하다