Dynamic Programming

Dynamic Programming 구조

 

다이나믹 프로그램밍 이라고 부르는 dp 알고리즘은 배열을 이용하여 각 경우의 수마다 최적의 값을 구할때마다 저장하여 다시 계산하지 않고 값을 불러옴으로써 불필요한 연산을 줄이는 알고리즘 입니다. 피보나치 함수 문제로 예를 들면 f(0) = 0, f(1) = 1, f(2) = f(1) + f(0), f(3) = f(2) + f(1) 이며 식으로 표현하면 f(n) = f(n-1) + f(n-2) 입니다. f(4) = f(3) + f(2)을 풀어서 쓰면 결국 이미 계산했던 f 함수의 값을 또 계산하게 됩니다. 그래서 임의의 배열에 f(1 .... n)까지의 값을 한번 올때마다 값을 계산해서 저장합니다.

DP 배열 반복문을 이용한 방법

dp[0] = 0;
dp[1] = 1;
for (i = 2; i < n + 1; i++)
{
    dp[i] = dp[i - 1] + dp[i - 2];
}

DP 재귀함수를 이용한 방법

int f(int n)
{
	if (n == 0)return 0;
	else if (n == 1)return 1;
	else if (dp[n] != 0)return dp[n];
	else return f(n - 1) + f(n - 2);
}

DP 계산 방법은 위와같이 두가지 방법으로 나뉘며 재귀함수를 이용할때 가장 중요한 부분은 if (dp[n] != 0) 조건에서 이미 계산된 값은 바로 리턴 하는 것 입니다.

마무리

오늘은 dp 알고리즘 알아보았으며 복잡한 문제는 2차원 dp나 그래프 탐색과 응용해서 많이 쓰입니다. 다른 알고리즘과 혼합해서 쓰이는 경우가 많으니 잘 숙지 하시길 바랍니다.