[바미] 동적 계획법(Dynamic Programming).
일반적으로 우리가 사용하는 "dynamic"이나 "programming"라는 단어가 있어 'Dynamic Programming' 과 관련이 있을 것 같지만 실제로는 아무련 관련이 없습니다.
동적 계획법은부분 문제를 통해 큰 문제를 재귀적으로 해결하려고 할 때 중복되는 부분 문제들이 많이 발생하여 불 필요하게 같은 계산이 반복될 때 사용됩니다.
이항 계수를 계산하는 공식은 아래와 같은 공식이 성립하게 되는데
bino(i, j) = bino(i-1, j-1) + bino(i, j-1)
위 식에 대해 생각해보면 알 수 있듯이 주어진 i과 j에 대해 두 문제로 나눠가면서 계산했을 때 밑으로 내려가면서 중복되는 식이 점점 더 많이 발생함을 알 수 있습니다.
i과 j의 크기가 커질 수록 중복되는 계산 역시 많아지는 데 그 양은 지수적으로 증가하기 때문에 큰 수에 대한 이항 계수는 단순한 재귀 호출로는 너무나 많은 시간이 들죠.
따라서 이 때 동적 계획법의 memoization을 이용하는 것인데, 그 방식은 그냥 매번 새로운 계산을 할 때마다 그 계산을 어떤 자료 구조에 기록해 놓는 것입니다. 그러면 그 계산값이 필요할 때마다 배번 함수를 호출해 다시 계산하는 것이 아니라 그 자료를 참조해 바로 그 값을 얻는 방식입니다.
이 방식을 사용하면 수십 번, 수천 번의 중복되는 계산도 한 번으로 줄일 수 있기 때문에, 계산양이 획기적으로 줄어들게 됩니다.
구현
이제 코드로 구현해볼까요?
int bino(int n, int r) {
//base case
if (r == 0 || n == r) return 1;
return bino(n - 1, r - 1) + bino(n - 1, r);
}
파스칼의 삼각형을 이용하여 위 값이 맞는지 확인해보죠.
이것이 메모이제이션을 사용하지 않았을 때 해결방법입니다.
이 때는 겹치는 부분이 발생하게 되어 i와 j의 크기가 커질수록 함수 호출이 기하급수적으로 늘어나게 되는 문제점이 있습니다.
메모이제이션(Memoization) 사용 시
메모이제이션 사용 시 한 번 계산한 값을 저장해 뒀다 재활용하기 때문에 위와 같이 중복이 제거되는 모습을 볼 수 있습니다.
long long cache[200][200] = { 0, };
long long bino(int n, int r) {
if (cache[n][r] > 0)return cache[n][r];
if (n == r || r == 0) return cache[n][r] = 1;
else return bino(n - 1, r) + bino(n - 1, r - 1);
}
int main(void) {
int n, r;
scanf("%d %d", &n, &r);
printf("%lld\n", bino(n, r));
}이와 같은 방식을 이용해 최적화하는 과정을 동적 계획법이라 합니다.
함수의 반환 값이 그 입력 값만으로 결정되는 경우에만 사용할 수 있는데 이를 referential transparent function(참조적 투명 함수)라고 부릅니다.
시간 복잡도
시간 복잡도를 계산이 다소 복잡하다고 생각할 수 있지만, 간단하게 계산할 수 있는 방법이 있습니다.
(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)
메모이제이션을 적용한 bino() 함수의 시간 복잡도를 구하면 다음과 같습니다.
부분 문제의 최대 수 : O(n^2) ; n^2 ( r = n )
부분 문제를 풀 때 : O(1) ; 반복문이 필요 없다.
따라서 O(n^2)xO(1) = O(n^2) 입니다.
즉, 메모이제이션을 사용하지 않았더라면 20 C 10을 계산할 때 호출이 369511번 걸리지만, 위의 코드를 사용한다면 201번으로 획기적으로 호출 횟수를 줄일 수 있게 됩니다.
참고