그리디 알고리즘 (Greedy Algorithm)

Greedy 는 '탐욕스러운, 욕심 많은' 이란 뜻을 가진 단어다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장의 눈앞에 보이는 최적의 선택을 통해 최종적인 해답에 도달하는 방법이다.

당장 눈앞에 보이는 최적의 선택만을 고려하기 때문에, 항상 최적해를 보장하지는 않는다. 대신 최적해와 가까운(근사적인) 해을 구할 수 있다. 이렇게 어떤 최적화 문제에서 근사값을 찾는 알고리즘을 근사 알고리즘(apporoximation algorithm)이라고 한다. 근사 알고리즘은 항상 최적해를 보장하지는 않지만, 비교적 빠른 시간에 실행되면서 일정 수준 이상의 해를 보장할 수 있다는 장점이 있다.

탐욕 알고리즘이 항상 최적해를 보장하기 위해서는 다음 2가지 조건이 성립되어야 한다.

탐욕적 선택 속성
각 단계에서 최적의 선택을 하면 전체 문제의 최적해를 구할 수 있음
최적 부분 구조
부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구성할 수 있음

탐욕적 선택 속성과 최적 부분 구조 두 가지를 모두 만족하는 문제를 매트로이드(Matroid)라고 한다. 즉, 매트로이드 문제에 대해서는 그리디 알고리즘이 항상 최적해를 보장한다. 그렇기 때문에 매트로이드 문제에 탐욕 알고리즘을 사용한다면 최적해를 빠르게 구할 수 있다.

그리디 알고리즘으로 최적해를 구할 수 있는 경우
거스름돈 문제를 생각해보자. 편의점에 500,100,50,10 원의 동전 종류가 있고, 동전의 개수에 대한 제한이 없을 때, 거스름돈의 동전의 개수를 최소한으로 하는 방법을 찾는 문제이다. 이 경우 그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있다. 이러한 문제가 바로 매트로이드 문제이다.

그리디 알고리즘으로 최적해를 구할 수 없는 경우 (근사해만 찾을 수 있는 경우)
배낭 문제를 생각해보자. 총 3개의 물건, 30kg 5000만원, 25kg 4000만원, 10kg 3000만원인 물건이 있다고 할 때, 35kg 의 용량인 가방에 가장 많은 가치를 가지도록 물건들을 담는 문제이다.
그리디 알고리즘의 경우엔 30kg 5000만원을 택하겠지만, 최적해는 25kg 와 10kg 물건을 선택하여 총 9000만원의 가치를 담는 것이다. 즉, 이 문제는 매트로이드가 아니므로, 탐욕 알고리즘이 항상 최적해를 보장하지는 않는다. 대신 빠르게 근사해를 찾을 수 있다.