7-1. 동적 계획법(Dynamic Programming)

1. 이항 계수(조합 ; Combination), 경우의 수

(1) 5개의 공 중에서 2개를 뽑는 경우의 수는?

 

(2) 코드로 구현하기

#include <iostream>
#include <windows.h>

using namespace std;

int combination(int n, int r)
{
	if (r == 0 || n == r)
		return 1;

	return combination(n - 1, r - 1) + combination(n - 1, r);
}

int main()
{
	__int64 start = GetTickCount64();

	int num = combination(45, 6);

	__int64 end = GetTickCount64();

	cout << end - start << " ms";
}

단순한 코드인데 출력값을 보면 시간이 꽤 걸리는 것을 알 수 있다.

조합을 작게 쪼게며 계산하는 과정에서 동일한 조합을 여러 번 계산했기 때문이다.

(같은 계산을 몇 십만회 반복)

 

즉 계산을 중복하지 않게 되면 리소스를 아낄 수 있을 것이다.

(이미 구한 값을 임시 저장소에 저장하는 방식으로)

 

2. 동적 계획법

동적 계획법을 사용할 때는 아래의 절차를 따른다.

메모이제이션이 핵심이다.

 

(1) 예외 사항

수식에 적용되는 예외 사항을 점검한다.

 

(2) 캐시를 확인(Memoization)

이미 답을 구한 적 있으면 결과를 즉시 반환한다.

 

(3) 새로 답을 구해 캐시에 저장하기

이미 답을 구한 적이 없다면 캐시에 저장한다.

int cache[50][50];

int combination(int n, int r)
{
	if (r == 0 || n == r) // 공을 안뽑거나 nCr에서 n = r이면 1임
		return 1;

	int& ret = cache[n][r];

	if (ret != -1) // 답을 구한 적이 있다면 ret을 반환
		return ret;

	return ret = combination(n - 1, r - 1) + combination(n - 1, r);
}

그리고 다시 코드를 실행하면 굉장히 빠른 속도로 작동하는 것을 알 수 있다.