Dynamic Programming
Dynamic Programming 은 분할 정복 기법과 유사하다.
분할 정복 기법은 문제를 여러개의 subproblem으로 나누고, 각 subproblem을 해결할 후, 각 subproblem의 해답을 이용하여 원래 문제의 해답을 계산한다. 그러나 각 subproblem이 독립적이지 않고, 서로 연관되어 있는 경우에는 매우 많은 반복연산이 이루어지고, 이로 하여금 많은 수행시간이 필요해진다.
하지만 Dynamic Programming은 분할정복 기법과 달리 Memoization 즉, 기억을 사용한다.
이말은 재귀적으로 문제를 해결하면서 해결한 작은 문제의 해답을 테이블(배역)에 저장한다는 의미이다. 큰 문제를 해결하면서 작은 문제를 해결할 필요가 있는 경우 그 작은 문제가 이미 해결되었는지를 확인하고 해결되었으면 테이블에 저장된 작은 문제의 해답을 사용하고 그렇지 않으면 recursion으로 문제를 계속 해결해 간다. 테이블에는 초기값을 설정해두어 해당 문제가 해결되었는지 안되었는지 분간할 수 있게 한다.
Dynamic Programming의 문제해결방법은 반복연산을 제거하는 것에 있다. 이것을 Bottom-Up Approach라고 한다. 작은 문제부터 시작하여 작은 문제를 해결할 후, 그 해답을 테이블에 저장하고 큰 문제를 해결하면서 작은 문제의 해답을 사용하는 것이다.
cf) Top-Down Apporach는 재귀 base
동전 교환문제
문제 : 서로 다른 단위의 동전이 주어졌을 때, 거스름돈을 동전의 개수가 최소가 되도록 교환해주려고 한다. 이때 교환해 주는 동전의 최소 개수와 교환해 주는 동전의 조합을 계산하시오. 단, 모든 단위의 동전은 무수히 많다고 가정한다.
동전의 종류 : 1원, 5원, 10원, 21원, 25원
거스롬돈 : 63원
위와 같이 조건이 주어졌을때, 먼저 동전 조합의 구조를 분석해야한다.
여기서는 거스름돈 63을 만들기 위한 조합을 생각한다.
25원 동전을 사용할 때는 38원이 더 필요
21원 동전을 사용할 때는 42원이 더 필요
10원 동전을 사용할 때는 53원이 더 필요
5원 동전을 사용할 때는 58원이 더 필요
1원 동전을 사용할 때는 62원이 더 필요
그럼 여기서 25원 동전을 사용할 경우 38원을 구성하는 조합도 이와 같은 방법으로 생각할 수 있다.
25원 동전을 사용할 때는 13원이 더 필요
21원 동전을 사용할 때는 17원이 더 필요
10원 동전을 사용할 때는 28원이 더 필요
5원 동전을 사용할 때는 33원이 더 필요
1원 동전을 사용할 때는 37원이 더 필요
이 과정을 일반화 하여 생각해 보면 다음과 같다.
동전의 종류: n 가지
거스름돈 : k원
그리고 C(k)를 k원을 바꿀 때, 최소 동전의 개수라고 한다면 이렇게 표현할 수 있다.
이것을 재귀식으로 표현하면 이렇다.
여기서 K<0인 경우 무한대로 둔 이유는 만약 K가 음수라면 거슬러 줄 수 있는 돈이 없는데 이때 min()에서 해당 값을 선택하지 못하게 하기 위해서 이다.
이렇게 재귀적으로 해결할 때 우리는 C(k)값을 테이블에 저장해야한다. 그래야 같은 계산을 또 반복하지 않기 때문이다. 동전계산 문제에서는 최소값으로 선택된 동전갯수와 마지막에 추가한 금액을 저장하면 된다.
그럼 이와 같은 테이블이 완성된다.
거스름 돈이 13인 경우를 예로 들자면,
10원 동전을 사용할 때는 3원이 더 필요
5원 동전을 사용할 때는 8원이 더 필요
1원 동전을 사용할 때는 12원이 더 필요
3원은 동전 3개 필요, 8원은 동전 4개 필요, 12원은 동전 3개 필요 하기 때문에 13의 경우 동전 갯수의 최소값은 4가 되고 마지막 더해진 동전의 경우 1원부터 차례로 올라가 10원이 된다.
이렇게 테이블을 사용하면 같은 계산을 계속 반복해야하는 재귀함수만 사용할 때보다 계산의 효율이 훨씬 더 올라간다.
