[BK]알고리즘 중급1 - 그리디 알고리즘

그리디 알고리즘

(greedy algorithm)

- 순간마다 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘

- 최종적으로는 답이 아닐 수도 있음

거스름돈 문제

- 최소의 동전과 지폐를 사용하여 N원을 거슬러주는 문제

(ex) 1, 5, 10, 100, ... 으로 7570원

-> 그리디

(ex) 1, 4, 5 으로 12원

-> 그리디 X, DP

동전0

Ai는 Ai-1의 배수 -> 그리디 알고리즘 성립