그리디(Greedy)/탐욕적 알고리즘

그리디 알고리즘

현재 상황에서 당장 가장 좋아보이는 상황만을 선택하는 알고리즘

• 최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많음 → 최적의 해에 가장 가까운 근사 해를 구할 수 있음

ex) 루트에서 출발해서 단말 노드까지 가는 경우, 거쳐가는 노드의 합이 가장 큰 경우 구하기

1. 완전탐색으로 풀기
   • 최적의 해: 10 (1→4→5)
   • 모든 상황을 고려해야 함
2. 그리디 알고리즘으로 풀기
   • 매 상황에서 단순히 가장 큰 노드를 선택: 8 (1→5→2)
   • 모든 경우의 수를 고려하지 않아도 되지만, 최적의 해는 아니다!

[접근 방식]

1. 방법 고안하기: 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안

2. 정당성 확인하기: 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인(증명 단계)

 

ex) 거스름돈 문제

카운터에 500원, 100원, 50원, 10원짜리 동전이 무수히 많이 존재할 때, 손님에게 6,480원을 거슬러 주어야할 때 동전 개수의 최솟값은?

 

해결방법: 가장 큰 화폐 단위부터 거슬러주기 → 500원, 100원, 50원, 10원 순으로 거슬러주기

 

1단계) 500원 거슬러주기: 6480/500 = 12...480 → 12개

2단계) 100원 거슬러주기: 480/100 = 4...80 → 4개

3단계) 50원 거슬러주기: 80/50 = 1...30 → 1개

4단계) 10원 거슬러주기: 30/10 = 3 → 3개

총 12+4+1+3 = 20개

﹡화폐 단위가 배수 관계에 속하기 때문에 그리디 알고리즘을 사용해서 최적의 해를 찾을 수 있음

 

만약, 120원을 거슬러 주어야 할 때 80원, 60원, 10원 동전이 있는 경우,

- 최적의 해: 60원*2 = 120원으로, 2개의 동전 필요

- 그리디 알고리즘 풀이로 80원부터 거슬러 준다면 총 5개의 동전 필요하므로 그리디 알고리즘으로 최적의 해 찾을 수 없음