그리디 알고리즘(탐욕법, 욕심쟁이법 으로도 불립니다)은

**“현재 상황에서 가장 최적인 답을 찾는 알고리즘”**입니다.

“greedy”는 “탐욕”, “욕심쟁이”를 뜻하는 영단어입니다.

예시 문제를 하나 생각해보겠습니다.

잔돈의 액수가 주어지면, 가장 최소한의 동전을 사용하여서 잔돈을 반환하시오.

현재 우리나라에서 쓰이는 동전은 4가지로,

500원, 100원, 50원, 10원이 있습니다.

(편의상, 잔돈의 일의 자리 수는 0임을 보장하겠습니다.)

이 문제를 푸는 방법은 하나입니다.