[C] 동적 계획법 (DP; Dynamic Programming)

동적 계획법이란 복잡한 문제를 부분적인 문제(subproblem)로 나누어 푸는 방법을 말한다

 

예를 들어,

1번 줄에서부터 10번 줄까지의 어떤 조건에 따라 계산을 하는데

2번 줄에서의 계산 방식과 7번 줄에서의 계산 방식이 동일하다고 할 때 생각해볼 수 있다

 

동적 계획법은 분할 정복과 같은데, 분할 정복은 계산한 부분 문제를 한 번만 쓰기 때문에 메모이제이션이 필요하지 않다

 

---

 

메모이제이션이 무엇인가 ?

 

void DFS(n)
{
	if(n == 1 || n == 2)
    	...
 
	if (DP[n] == 0)
  	{
   		...
  	  	DFS(n-1);
		DFS(n-2);
   		DP[n] = DP[n-1] + DP[n-2];
   		...
  	}
 }

 

위의 코드에서 재귀함수를 활용하여 1~n까지의 경우를 확인하는데,

DP배열에 이미 확인한 부분을 Memo 하여 같은 계산을 반복하지 않도록 하는 것이다

 

---

 

위와 같은 예시를 n에서 1까지 내려왔다고 하여 TOP - DOWN 방식이라고 하고

BOTTOM - UP 방식은 다음과 같다

 

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

 

피보나치 수열을 DP를 적용하여 구사한 코드이다

0에서 n까지 올라가며 값을 구하는 것을 볼 수 있다

시간 복잡도는 같지만 TOP - DOWN 방식의 시간이 좀 더 길다고 일반적으로 알려져 있다

 

---

 

주의해야 될 점이 무엇이 있나 ?

 

1. 초기화

첫 번째 코드를 보면, DP[n] == 0의 조건으로 판단을 하는 경우가 있다

이는 DP 배열을 0으로 초기화 하였기때문에 가능한 조건문임을 알아야 한다

만약 0의 값을 쓰는 메모이제이션이라면 통상 -1로 초기화를 하곤 한다 (또는 INT_MAX)

 

2. 가이드라인

메모이제이션을 몇 차원으로 할 것인가?

변수의 의미는 무엇인가?

이를 생각하여 점화식으로 재귀 또는 for문 계산을 하면 된다

 

 

-all about coding

 

https://snupi.tistory.com/200 (Javascript 언어)