[알고리즘 이론] 그리디 알고리즘(탐욕법)

---

그리디 알고리즘(탐욕법)은 말 그대로,

지금 최선인 것 처럼 보이는 선택을 하여 문제를 해결하는 알고리즘이다.

욕심쟁이가 가장 최고인 방법을 고집하는 느낌이다.

그러나, 그리디 알고리즘은 항상 옳은 해답만 내놓지 않는다.

 

가장 흔한 예시인 동전 거슬러주기를 생각해보자.

500원 400원 100원 단위를 1500원을 거슬러주는 방법 중 가장 적은 동전을 사용하는 방법은 어떻게 코딩할까?

가장 큰 수인 500으로 나누고 나머지는 그 아래 400원, 100원짜리 순으로 나누면 최소의 동전으로 줄 수 있는 거스름돈이 나올 것이다.

 

하지만, 800원을 거슬러준다고 생각해보자.

공식대로라면, 500원짜리 하나, 100원짜리 3개로 총 4개의 동전을 거슬러 줄 것이다.

그러나, 400원짜리 2개를 주는 방법이 더 적다.

 

현재 최고인 것 처럼 보이는 가장 큰 수를 선택하는 방법이 결론은 적합하지 못한 결과를 일으킨다.

 

그렇기 때문에 그리디 알고리즘을 이용해 문제를 풀기 위해서는, 아래 두 가지 조건이 부합해야 한다.

 

1. 탐욕 선택 조건 (greedy choice property)

2. 최적 부분 구조 조건 (optimal substructure)

 

탐욕 선택 조건은 매번의 선택이 최선의 선택이어야 하는 것,

최적 부분 구조 조건은 그 부분의 최선의 선택이 어떠한 상황에서도 최선의 선택이어야 하는 것이다.