동적 계획법(Dynamic Programming)

문제를 여러개의 작은 문제로 나누고, 작은 문제의 해를 이용하여 더 큰 문제의 해를 찾는 문제해결 패러다임 이다.

 

 

 

 

 

설명을 쉽게 하기 위하여 간단하게 예를 들어보자.

 

동적 계획법을 이용하는 대표적인 문제는 동전 거스름돈 문제이다.

 

이 문제는 거슬러 받는 동전의 개수를 가장 적게 받아야 하는 문제이다.

 

 

 

 

 

동전의 종류는 1원, 3원, 7원, 10원이 있고 거슬러 받는 돈이 총 14원이라고 하자.

 

 

생각하기 가장 쉬운 방법은, 액수가 가장 큰 동전부터 채워서 주는 것이다.

 

이렇게 줄 경우

10원 1개 + 3원 1개 + 1원 1개   ==>>  총 3개의 동전을 주게 된다.

 

 

과연 최소한의 개수로 동전을 준 것이 맞을까?   질문의 답은 '아니오' 다.

 

7원짜리 2개를 주는 방법이 동전을 더 적게 줄 수 있다.

 

 

 

만약, 동전의 종류가 굉장히 다양하고 거스름돈의 값이 크다면 우리는 어떻게 이 문제를 풀 수 있을까?

 

이러한 경우에 쓰이는 해법이 동적 계획법(Dynamic Programming) 이다.

 

 

위의 문제에 동적 계획법을 적용해보자.

 

어떻게 해서 7원짜리 2개를 주는 방법이 나온 것일까?

 

 

동전의 종류는 1원, 3원, 7원, 10원이 있다고 하였다.

 

 

 

1. 작은 문제로 쪼개어 생각한다.

 

목표인 14원에서 각 동전의 액수만큼 뺀다면

 

ㄱ. (14 - 1)원  ==>>  13원의 해 + 1원짜리 1개

ㄴ. (14 - 3)원  ==>>  11원의 해 + 3원짜리 1개

ㄷ. (14 - 7)원  ==>>  7원의 해 + 7원짜리 1개

ㄹ. (14 - 10)원  ==>>  4원의 해 + 10원짜리 1개

 

이렇게 4가지의 경우의 수가 나온다.

 

저 중에서 가장 작은 값이 최종 해가 되는 것은 자명하다.

 

각 경우의 수 마다 존재하는, 목표보다 더 작은 문제의 해를 구해야 함을 생각한다.

 

 

 

2. 생각할 수 있는 가장 작은 문제의 해를 찾는다.

 

거슬러 받는 돈이 0원일 경우  ==>>  동전을 거슬러 줄 필요가 없다.

거슬러 받는 돈이 1원일 경우  ==>>  1원짜리 동전 1개를 주면 된다.

거슬러 받는 돈이 2원일 경우  ==>>  1원짜리 동전 2개를 주면 된다.

 

그 이상의 경우는 다음 단계에서 처리할 것이다.

 

 

 

3. 작은 문제의 해를 이용하여 더 큰 문제의 해를 찾아나간다.

 

3원의 해는

ㄱ. (3 - 1)원의 해 + 1원짜리 1개  =  3

ㄴ. (3 - 3)원의 해 + 3원짜리 1개  =  1

 

두 경우 중 작은 값인 1이다.

 

 

4원의 해는

ㄱ. (4 - 1)원의 해 + 1원짜리 1개  =  2

ㄴ. (4 - 3)원의 해 + 3원짜리 1개  =  2

 

두 경우 중 작은 값인 2이다.

 

                          .

                          .

                          .

 

 

이렇게 진행하다보면 14원일 때의 경우의 수가 나올 것이고,

 

이전에 구해놨던 해를 계속 이용하여 가장 작은 값을 최종 해로 선택하면 된다.

 

 

 

 

 

이 알고리즘을 문제에 적용시키려면 결과적으로 점화식을 찾아야 한다.

 

위의 동전 거스름돈 문제도 결국 점화식으로 표현해보면

 

N  :  동전의 개수

M  :  거슬러줄 액수

cost[ i ]  :  각 동전의 액면가를 저장한 배열

DP[ i ]  :  i 일때 의 해를 저장한 배열

 

for i = 0 to N

  for j = cost[ i ] to M

    DP[ i ]  =  MIN ( DP[ i ] ,  DP[ j - cost[ i ] ]  +  1 )

 

 

으로 표현할 수 있다.