그리디 알고리즘

매 단계에서 지금 당장 가장 좋아 보이는 것을 고르고, 한 번 고른 것은 되돌리지 않는 방법이다. 빠르고 단순하지만 지금의 최선이 전체의 최선이 된다는 조건이 성립하는 문제에서만 맞는 답을 낸다. 거스름돈을 큰 동전부터 내는 방식이 예다 — 500 · 100 · 50 · 10원 체계에서는 맞지만, 동전이 1 · 3 · 4원이고 6원을 거슬러야 하면 4+1+1(3개)을 내서 3+3(2개)을 놓친다.