다이나믹 프로그래밍 컴퓨터 공학적 사고를 위한 이해2

29 Jun 2021 | C++

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어서 푸는 방식의 알고리즘이다. 동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 낸다는 점에서 분할 정복(Divide & Conquer, D&C)과 비슷하다. 하지만 가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될수가 없다는 점이다.

다시 말하면, 동적 계획법과 분할 정복의 차이는 문제를 나누는 방식이다. 동적 계획법에서는 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용함으로써 속도의 향상을 시킬 수 있다. 이때 이미 계산한 값을 저장해 두는 메모리를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다.

1. 동적 계획법의 조건

두 가지 속성을 만족해야 동적 계획법으로 문제를 풀 수 있다.
- Overlapping Subproblem : 겹치는 부분(작은) 문제
- Optimal Substructure : 최적 부분구조

2.Memoization

동적 계획법에서 각 문제는 한 번만 풀어야 한다. 중복되는 부분 문제를 여러번 풀지 않는다는 뜻이다. Optimal Substructure를 만족하기 때문에 같은 문제는 구할 때마다 정답이 같다. 따라서 정답을 한 번 구했으면 그 정답을 캐시에 메모해놓는다. 이렇게 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다. 이를 메모이제이션(Memoization)이라고 한다.

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

이런식을 구현하면 될텐데, 여기에서 이미 계산한 부분문제의 경우 그 값을 그대로 사용하는 코드를 추가해야 한다. memo배열에 값이 0이면 답을 구하지 않았다는 뜻이고, 0이 아니면 답을 구한적이 있다(이전의 호출에서 해당 값을 구함)는 뜻이므로, 이를 활용하면 된다.

int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
    	return n;
    } else {
        if (memo[n] > 0) {	// memo의 값이 0이 아니면
            return memo[n];	// 그 값을 그대로 사용
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

3.동적 계획법 구현 방식

Top-down : 큰 문제를 작은 문제로 쪼개면서 푼다. 재귀로 구현
- 1. 큰 문제를 작은 문제로 나눈다.
- 1. 작은 문제를 푼다.
- 1. 작은 문제를 풀었으니, 이제 큰 문제를 푼다.

피보나치 문제로 예를 들면, fibonacci(n)라는 문제를 풀기위해서 문제를 작은 문제로 나눈다.

fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다. 작은 문제를 푼다.
fibonacci(n-1)과 fibonacci(n-2)를 호출해 문제를 푼다. 작은 문제를 풀었으니, 이제 문제를 푼다.
fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 문제를 푼다.

Bottom-up : 작은 문제부터 차례대로 푼다. 반복문으로 구현
- 1.문제를 크기가 작은 문제부터 차례대로 푼다.
- 2.문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
- 3.작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
- 4.반복하다 보면 가장 큰 문제를 풀 수 있다.

똑같이 피보나치 문제로 예를 들면,

문제를 크기가 작은 문제부터 차례대로 푼다.

for (int i=2; i<=n; i++) 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
for (int i=2; i<=n; i++) 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
d[i] = d[i-1] + d[i-2]; 반복하다 보면 가장 큰 문제를 풀 수 있다.
d[n]을 구하게 된다.

int d[100];
int fibonacci(int n) {
    d[0] = 0;
    d[1] = 1;
    for (int i=2; i<=n; i++) {	// 2에서 부터 시작해서 n까지 반복
    	d[i] = d[i-1] + d[i-2];
    }
    return d[n];
}