탐욕법 (greedy)

매 순간마다 최선의 경우만을 골라간다

• 다른 경우는 고려하지 않는다
• 나중은 생각하지 않는다

예제

동전 거스름돈 문제

1. 10, 50, 100, 500원 동전을 무한하게 갖고 있다
2. 100, 400, 500원 동전을 무한하게 갖고 있다
   Q. 손님에게 800원을 거슬러주려고 할 때 동전을 최소한으로 주는 방법은?

1번
탐욕법으로 풀이 가능
500원을 우선으로 주고 나머지 주는 경우 생각

2번
탐욕법으로 풀이 불가능
반례 : (500x1, 100x3) 보다 (400x2)가 최소한의 방법임

즉, 이 문제가 그리디 문제인지 아닌지 판별부터가 어렵다
코테에서 수학적으로 그리디 문제인지 아닌지 판별할 시간이 없으므로
그리디 문제인지 아닌지 감을 익히는 것이 중요!

예제

boj 11047 동전 0
👉 문제 조건을 보면 A(i)는 A(i-1)의 배수라고 주어졌으므로 탐욕법 풀이가 가능함을 알 수 있다.

boj 1449 수리공 항승