그리디 알고리즘(Greedy, 탐욕법)

이번 포스팅에서는 그리디 알고리즘에 대해 알아보고자 한다.

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

 

따라서 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다.

🍀 거스름 돈 문제

거스름 돈으로 사용할 돈은 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

-> 그리디 알고리즘을 활용해 풀 수 있는 대표적인 문제

🍀 정당성 분석

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유 :

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

예) 800원을 거슬러 줘야 할 때 화폐 단위가 500원, 400원 100원이 있다고 하자. 만약 그리디 알고리즘으로 풀면 

=> 이처럼 그리디 알고리즘은 정당한지 검토할 수 있어야함.

 

* 다익스트라 최단 경로 알고리즘과 크루스칼 알고리즘도 모두 그리디 알고리즘에 속한다.

---

📚 참고 : 이것이 취업을 위한 코딩테스트다 with 파이썬