[Algorithm] 그리디 알고리즘(탐욕법)에 대해 쉽게 알아보자

💡 그리디 알고리즘

---

그리디 알고리즘은 한국어로 탐욕 알고리즘 이라고도 하며 결정해야 하는 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘을 말합니다. 이 방식의 한계점은 그 순간에는 최적일지도 모르지만, 최종적으로는 답이 아닐 수 있는 경우가 많기 때문에 그리디 알고리즘을 사용한 경우, 최적이라는 걸 입증하는게 쉽지 않습니다. 그래도 입증만 한다면 구현하는건 다른 알고리즘에 비해 쉬운 편입니다. 아래 문제를 보면서 이해해보도록 하겠습니다.

** 그래서 그리디 알고리즘으로 문제를 어떻게 푸는건가요?

그리디 알고리즘은 무조건 큰 수부터 채워서 최소값을 구하는 것입니다. 예를 들어 동전 문제가 있습니다. 만약, 177원을 만든다면 100원 1개 10원 2개 5원 1개 1원 2개의 동전을 주면 됩니다. 

 

💡 그리디 알고리즘 대표 문제

---

그리디 알고리즘을 이용하면 아주 쉽게 풀리는 문제를 가져와보았습니다.

https://www.acmicpc.net/problem/11047

11047번: 동전 0