[Algorithm] 그리디 알고리즘

그리디 알고리즘(Greedy algorithm) : 탐욕법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

그리디 알고리즘의 대표적인 예제는 거스름돈이다.

마트에 가서 현금으로 결제하면 직원은 우리에게 '가장 큰 화폐단위'부터 돈을 거슬러 준다.

그것이 가장 적은 화폐수로 거스름돈을 줄 수 있는 방법이기 때문이다.

 

정당성을 어떻게 보장하는가?

 

그리디 알고리즘의 정당성 : 그리디 알고리즘을 이용해도 '최적의 해'를 찾을 수 없는 경우가 많다.

 

거스름돈의 예에서, 어떤 화폐는 그것보다 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없나는 사실이 정당성을 증명한다. 

우리나라 화폐는 10, 50, 100, 500, 1000, 5000, 10000, 50000이다. 즉 배수로 증가함을 확인할 수 있다.

반면에, 600원짜리 화폐가 등장한다면 그리디 알고리즘의 정당성을 충족하지 못한다.

 

이처럼 그리디 알고리즘의 문제에서는 문제풀이 아이디어를 그리디로 접근했다면 이것이 정당한지를 검토할 수 있어야 한다.