동적 계획법

Dynamic Programming (DP)

 

 

Divde & Conquer 과 같이 문제를 작은 부분문제들로 쪼개는 과정을 거친다.

 

하지만 DP는 memoization을 사용한다는 차이점이 있다.

 

여기서 memoization이란 한 번 계산한 값을 저장해 두었다 재활용하는 기법을 의미한다.

 

 

종합하자면, Divide & Conquer은 부분 문제들이 서로 겹치지 않을 때 사용하기 좋다.

 

만약 동일한 부분 문제들이 계산 과정에서 여러 번 등장한다면, 중복 계산을 피하는 DP를 사용하는 것이 좋다.

 

 

이항 계수 (binomial coefficient) 계산을 예로 들어보자.

 

$$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} = (\binom{2}{0} + \binom{2}{1}) + (\binom{2}{1} + \binom{2}{2}) $$

 

계산이 중복되는 모습을 확인할 수 있다.

 

# Without memoization

int binom(int n, int k) {
	if (k == 0 || n == k) {
    	return 1;
    }
    
    return binom(n - 1, k - 1) + binom(n - 1, k);
}

 

 

# With memoization

vector<vector<int> > dp(100, vector<int>(100, -1);

int binom(int n, int k) {
	if (dp[n][k] != -1) {
    	return dp[n][k];
    }

	if (k == 0 || n == k) {
    	return dp[n][k] = 1;
    }
    
    return dp[n][k] = (binom(n - 1, k - 1) + binom(n - 1, k));
}

 

가능하지 않은 값으로 초기화해준 cache를 만들어 주고 사용을 할 때 초기화 해준 값이 변경되어있다면 바로 가져와서 쓰고 그대로라면 계산해서 넣어준다.

 

 

메모리를 희생하고 시간을 버는거지만, 공정한 trade off라기엔 효용이 너무 좋아진다.

 

 

대표격인 문제로는

 

10870번: 피보나치 수 5

 

11726번: 2×n 타일링

 

 

11055번: 가장 큰 증가 부분 수열