나보단 잘하자

그리디 알고리즘(탐욕법)은 말 그대로, 지금 최선인 것 처럼 보이는 선택을 하여 문제를 해결하는 알고리즘이다. 욕심쟁이가 가장 최고인 방법을 고집하는 느낌이다. 그러나, 그리디 알고리즘은 항상 옳은 해답만 내놓지 않는다. 가장 흔한 예시인 동전 거슬러주기를 생각해보자. 500원 400원 100원 단위를 1500원을 거슬러주는 방법 중 가장 적은 동전을 사용하는 방법은 어떻게 코딩할까? 가장 큰 수인 500으로 나누고 나머지는 그 아래 400원, 100원짜리 순으로 나누면 최소의 동전으로 줄 수 있는 거스름돈이 나올 것이다. 하지만, 800원을 거슬러준다고 생각해보자. 공식대로라면, 500원짜리 하나, 100원짜리 3개로 총 4개의 동전을 거슬러 줄 것이다. 그러나, 400원짜리 2개를 주는 방법이 더 적..