탐욕법(그리디 알고리즘)이란?

선택을 할 때마다 그 당시에 할 수 있는 가장 최선의 선택을 하는 알고리즘이다. 가장 쉬운 예는 돈을 지불하는 방식이다. 만약 어떤 물건을 샀고 그 가격이 1560원이라고 가정한다. 그럼 우리는 가장 적은 지폐와 가장 적은 동전을 사용해(동전갯수와 지폐갯수를 합했을 때 가장 적게 지불하려 함) 값을 지불하려 한다면 어떻게 할까? 처음에 1560원에서 1000원짜리 지폐를 이용하려 할 것이고, 남은 (1560-1000)560원에서 500원짜리 동전을 이용하려 할 것이고, 그 다음 남은 (560-500)60원에서 50원짜리 동전을 이용하려 할 것이고, 마지막으로 남은 10원은 10원짜리 동전을 이용하려 할 것이다. 만약 첫번째 선택에서 1560원을 1000원짜리 지폐를 사용하지 않고 500원짜리 동전을 이용해 지불하려 했다면 1000원에 해당하는 금액을 1000원짜리 지폐 하나로 지불할 수 있었던 상황이 500원짜리 두개로 지불하게 되는 상황으로 바뀌게 된다.