[알고리즘 개념] 동적계획법

 

동적 계획법

 

영어로 하면 Dynamic Programming이다.

큰 문제를 작은 문제로 나누어 푸는 문제를 일컬어 동저계획법이라고 한다.

이 점에서 분할 정복과 비슷하지만,

가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될 수가 없다는 점이다.

 

따라서 동적 계획법은 작은 문제의 결과를 저장해둔다.

이미 계산한 값을 저장해 두는 메모리를 캐시라고 하며 같은 문제가 다시 등장하였을 때 이를 이용하여 문제 해결 속도를 향상할 수 있다.

 

 

조건

 

작은 문제의 반복이 일어나는 경우. 단, 이 작은 문제의 결과는 같아야 한다.

즉, 어떤 문제가 여러 개의 부분 문제로 쪼개어질 수 있어야 하며 이 부분 문제는 같은 부분 문제이거나 재귀 알고리즘을 통해 해결되어야 한다.

 

 

피보나치수열

 

동적 계획법을 사용하는 가장 대표적인 예이다.

피보나치수열은 다음을 만족한다.

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

 

결걱 n번째 피보나치 수를 구하는 문제는 n-1과 n-2번째 피보나치 수를 구하는 문제와 같다.

따라서 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

 

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

이 코드는 피보나치 수를 재귀 호출을 이용하여 구하는 방식이다.

각각의 수에 대해 F(1)이 될 때까지 재귀 호출하기 때문에 이 경우 시간 복잡도는 O(2^n)과 같다. 

시간 복잡도가 이진트리의 탐색 속도와 같다는 것을 알 수 있다.

 

재귀 호출되는 것을 그림으로 표현하면 위와 같다.

노드들을 보면 중복된 수들이 많이 보인다.

이 중복된 수들을 저장하여 필요할 때마다 꺼내 쓸 수 있다면, 부분 문제의 가지를 모두 생략할 수 있다.

이경우 시간 복잡도는 (문제의 개수 x 문제 1개를 푸는 시간) 즉, O(n)과 같아진다.

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];
    }
}

이처럼 memo 배열을 이용하여 계산한 값들을 저장할 수 있고,

이미 계산한 값이라면 값을 그대로 사용하여 더욱 효율적으로 계산할 수 있다.

 

 

구현 방식

 

1. Top-down : 큰 문제를 작은 문제로 쪼개면서 푼다. 재귀로 구현

2. Bottom-up : 작은 문제부터 차례대로 푼다. 반복문으로 구현

 

문제에 따라 재귀로 구현하였을 때 더 깔끔한 코드가 나오는 것이 있고,

반복으로 구현하였을 때 더 깔끔한 코드가 나오는 것이 있기 때문에 잘 선택하여 구현하면 될 것 같다.

 

위의 피보나치 수를 두 가지로 구현해보면

1번 방식이 위에 나온 재귀를 이용한 방식이고

2번 방식은 다음과 같다.

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];
}