[알고리즘] 탐욕 알고리즘, The Greedy Approach

  미래의 결과를 예측할 수 없는 상황에서 지금 내가 할 수 있는 최선의 결정은 무엇일까? 매 선택마다 그 순간에 가장 좋다고 생각되는 것을 선택하는 것이다. 즉, 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달한다. 매 순간 가장 좋다고 생각되는 것을 선택하면 그것이 궁극적으로도 최적이 될 수도 있기 때문이다. 이러한 원리의 접근방식이 바로 Greedy Approach이다.

  하지만 이는 미래를 고려하지 않고 단지 그 순간에서의 optimal한 것을 선택한 것이므로, 그 해답이 궁극적으로 optimal라는 보장이 없다. 따라서 최적의 해답을 주는 알고리즘인지 검증하는 과정이 반드시 필요하다. 따라서 Greedy Approach 알고리즘의 구성은 다음과 같다.

 

<Greedy Approach 알고리즘 구성>

① 선택 절차, selection procedure

  : 현재 상태에서 가장 좋다고 생각되는 해답을 선택한다.

② 타당성 검증, feasibility check

  : 해로 얻은 해답을 solution set에 넣을지 말지 결정한다.

③ 해답 검증, solution check

  : 새로 얻은 solution set이 최종 해인지 점검한다. 즉 다른 해답을 더 모을지, 다 모은 것인지 검사한다.

 

  이 때 주의할 점은, greedy approach로 풀리지 않는 문제도 있다는 점이다. 동전의 개수가 최소가 되도록 거스름 돈을 주는 문제를 예로 들어보자.  거스름돈을 x라고 할 때, 탐욕 알고리즘에 따르면 값이 큰 동전부터 내림차순으로 동전을 x가 초과되지 않도록 내주다가 총 액이 x가 될 때 종료한다. 이 과정을 위에서 살펴봤던 3가지 구성으로 정리하면 다음과 같다.

 

① 선택 절차, selection procedure

  : 가장 큰 값의 동전을 선택한다.

② 타당성 검증, feasibility check

  : 이 동전을 추가할 경우 거스름돈 x원을 초과하는지 초과하지 않는지 검사한다.

③ 해답 검증, solution check

  : 선택한 동전들의 총 합이 거스름돈 x원과 일치하면 해답을 찾은 것이므로 종료한다.

 

  이 방법에 한국 동전을 적용시키면 항상 최적의 해답이 도출된다. 예를들어 230원을 거슬러 준다고 할 때, 500원은 230원을 초과하므로 x, 100원짜리 2개, 200원을 담은 상황에서 50원짜리를 넣으면 230원을 초과하므로 x, 10원짜리 3개 이렇게 최적의 답이 도출된다.

 

한국 화폐로 계산할 경우

 

  하지만, 만약 어떤 국가에서는 동전이 우리나라와 같이 500원, 100원, 50원, 10원, 1원짜리가 있지만 이에 더해 12원이라는 단위가 추가적으로 있다고 가정해보자. 이 경우 탐욕 알고리즘에 따르면 아래의 그림과 같이 100원짜리 2개,  12원짜리 2개, 1원짜리 6개 총 10개의 동전이 필요하다.

 

12원이라는 화폐단위가 존재하는 국가의 경우

 

  이는 최적의 결과가 아니다. 12원짜리를 사용하지 않고 100원짜리 2개, 10원짜리 3개를 사용할 경우 5개의 동전만 필요한, 더 좋은 최적의 결과가 존재하기 때문이다.

  따라서 greedy approach는 경우에 따라 풀리는 문제가 있고 풀리지 않는 문제가 있다는 것을 명심해야한다.

 

  이번 카테고리에서는 greedy approach 알고리즘을 적용할 수 있는 문제들인 최소 신장 트리(MST),  다익스트라의 최단거리, 프림 알고리즘 등에 대해 알아볼 예정이다.

 

[알고리즘] 최소비용 신장트리, Minimum Spanning Tree

[알고리즘] 프림 알고리즘, Prim's Algorithm | 설계 및 분석

 

[알고리즘] 크루스칼 알고리즘, Kruskal's Algorithm | 설계 및 구현코드

 

[알고리즘] 다익스트라 알고리즘, Dijkstra's Algorithm | 설계 및 분석, 구현코드