편집 요약 없음 |
|||
| 8번째 줄: | 8번째 줄: | ||
== 거스름돈 문제 == | == 거스름돈 문제 == | ||
그냥 이론을 설명하기에는 복잡하니, 예시를 보며 이해해 보자. | 그냥 이론을 설명하기에는 복잡하니, 예시를 보며 이해해 보자. | ||
리브레 제국의 화폐 체계는 영 이상해서, 이 나라의 상인들은 거스름돈 계산을 힘들어 한다. 국왕인 당신은 이러한 백성들을 어엿비 녀겨 거스름돈을 계산하는 프로그램을 만들기로 결심했다. | |||
이 나라에는 <math> x_1 </math>원, <math> x_2 </math>원, <math> \cdots , x_i </math>원 짜리 동전이 있고, 거슬러 주는 동전의 개수는 최대한 줄여야 한다. | |||
=== Top-down method === | === Top-down method === | ||
2016년 5월 20일 (금) 00:50 판
Dynamic Programming, DP.
개요
동적 계획법은 어떤 최적화 문제를, 작은 부분 문제로 나누어 차례대로 해결하는 알고리즘을 말한다.
이름이 Dynamic Programming이지만 그닥 역동적인 알고리즘은 아닌데, 예산을 따오기 위해 멋진 이름을 지었다고 카더라(...). 또한 Programming은 컴퓨터 프로그래밍을 의미하는 것이 아니고, 선형계획법처럼 최적화 문제의 해결 방법이라는 의미이다.
거스름돈 문제
그냥 이론을 설명하기에는 복잡하니, 예시를 보며 이해해 보자.
리브레 제국의 화폐 체계는 영 이상해서, 이 나라의 상인들은 거스름돈 계산을 힘들어 한다. 국왕인 당신은 이러한 백성들을 어엿비 녀겨 거스름돈을 계산하는 프로그램을 만들기로 결심했다.
이 나라에는 [math]\displaystyle{ x_1 }[/math]원, [math]\displaystyle{ x_2 }[/math]원, [math]\displaystyle{ \cdots , x_i }[/math]원 짜리 동전이 있고, 거슬러 주는 동전의 개수는 최대한 줄여야 한다.