동적 계획법(Dynamic Programming)

개념 요약

• 한가지 문제를 한번만 풀도록 만드는 알고리즘이다.
• 문제를 여러번 풀어 반복하지 않도록 하여 실행시간을 줄여준다.
• 규칙에 대한 점화식을 도출하여 푸는 방법이다.
• Memoization : 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것.

 

Ex. 피보나치 수열

TOP-DOWN

int	fiboData[100] = {0, };

int	fibo(int n)
{
	if (n <= 2)
		return (1);
	if (fiboData[n] == 0)
		fiboData[n] = fibo(n - 1) + fibo(n - 2);
	return (fiboData[n]);
}

 

BOTTOM-UP

int	fiboData[100] = {0, };

int	fibo(int n)
{
	fiboData[0] = 0;
	fiboData[1] = 1;
	for (int i = 2; i <= n; ++i)
		fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
	return (fiboData[n]);
}