동적계획법(Dynamic Programing)이란?
복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법
동적계획법은 분할된 모든 경우의 수를 검토한다.
중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다.
최소 경로 비용 합 ( Minimum Path Sum )
타일 안에서 이동은 오른쪽이나 아래쪽만 가능하다. 각 타일에 비용이 할당되어 있을 때, 시작부터 끝까지 가는 최소 비용을 구하라.
Top-Down
목적지에 도달할 수 있는 경우의 수는 A와 B 두 가지이다. A와 B의 비용을 구해 최소값을 선택하면 된다.
A는 C와 D의 최소비용이다. Top-Down 방식을 적용하면 이렇게 하나씩 구하면 된다. 중복되는 경로의 비용을 저장하여 최소비용을 검토한다고 해도 꽤나 복잡하다.
Bottom-Up
Top-Down 방식은 보통 재귀함수로 구현된다. 재귀함수는 같은 함수를 반복적으로 호출하는 방식이다. 함수는 영역(local)을 갖는다. 그래서 많이 호출되면 그만큼 스택메모리를 잡아먹는다. 엄청나게 큰 수를 구하고 싶으면 그만큼 많은 함수가 호출되므로 스택오버플로우가 발생할 수 있다.
시작부터 모든 타일의 최소비용을 하나씩 구해본다.
타일 안에서 이동은 오른쪽과 아래쪽만 가능하므로 가장 위쪽과 왼쪽의 최소비용은 정해져 있다. 이제부터는 오른쪽과 아래쪽 중 최소(min)비용을 선택해서 타일에 할당된 비용과 더해주기만 하면 된다.
4와 3 중 최소는 3이다. 타일에 할당된 비용이 4 이므로 4 + 3을 하여 7이 된다. 이런 과정을 모든 타일에 반복한다.
이와 같이, 모든 계산이 완료되면 최소비용을 구할 수 있다.
참고자료
'알고리즘 > 알고리즘' 카테고리의 다른 글
| [동적계획법] Decoding Ways (0) | 2021.11.05 |
|---|---|
| [동적계획법] 최소 동전 개수 ( Min Coin Change ) (0) | 2021.11.05 |
| [동적계획법] 최소비용 계단 오르기 ( Min Cost Climbing Stairs ) (0) | 2021.11.04 |
| [동적계획법] 피보나치 수열 (0) | 2021.11.04 |
| Greedy 예제(7) Gas Station (0) | 2021.10.29 |