[DP] Chapter 01. 동적 계획법

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/fac912f7ab6a8e859eb14e7e89e9c0cff20caaf7

동적 계획법 입문 · developeSHG/Data_Structure-Algorithm@fac912f

 

 

---

 

 

Dynamic Programming

문제를 쪼개서 해결하는데, 과정속에 반복되는 작업을 cache를 재사용해 불필요한 연산을 줄이는 것.

즉, DP는 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

 

왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.

 

---

 

메모이제이션 (memoization) - 속도를 빠르게하는 최적화 기법

반복되는 연산에 대해선 한 번만 구해주고, 그 이후엔 이미 저장된 결과물을 재활용해서 속도를 빠르게 한다.

물론 메모이제이션을 하기 위해서 cache 데이터를 할당하는 것 자체가 상당히 부담이 될 수도 있다.

하지만, 이전 hash table 학습에서도 살을 내주고 뼈를 취한다 라는 전략을 사용했던 것처럼, 메모이제이션도 어느정도 메모리 손실을 감수하더라도 캐쉬 값을 저장해서 재활용하는 것이 효율적이기 때문에, 메모리를 크게 잡고 활용한다.

 

메모이제이션을 사용하기 이전엔 tick이 359ms가 걸렸고, 사용 이후 0ms가 걸렸다.

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
#include <thread>
#include <windows.h>

// 오늘의 주제 : 동적 계획법 (DP)

// 메모이제이션 (memoization)
int cache[50][50];

int combination(int n, int r)
{
	// 기저 사례
	if (r == 0 || n == r)
		return 1;

	// 이미 답을 구한 적 있으면 바로 반환
	int& ret = cache[n][r];
	if (ret != -1)
		return ret;

	// 새로 답을 구해서 캐시에 저장
	return ret = combination(n - 1, r - 1) + combination(n - 1, r);
}

int main()
{
	::memset(cache, -1, sizeof(cache)); // -1로 초기화

	__int64 start = GetTickCount64();

	int lotto = combination(45, 6);

	__int64 end = GetTickCount64();

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