[Algorithm] Greedy

Greedy 알고리즘

그리디(Greedy) 알고리즘은 Greedy(탐욕스러운)라는 이름 그대로 선택의 순간마다 현재 상황에서 가장 최적이라고 생각하는 해를 선택하는 방법이다.

그리디 알고리즘은 국소 최적해(locally optimal solution)를 찾음으로써 최종적으로 전역 최적해(global optimal solution)를 구하는 방법으로, 현재의 선택이 앞으로 끼칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘은 최적해를 보장하지 않기 때문에 특수한 조건에서 사용된다.

그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있는 경우, 그리디는 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.

그리디 알고리즘 문제에서는 문제 해결을 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

 

정당성 분석

1. 탐욕 선택 속성 (Greedy Choice Property)
   : 이전의 선택이 이후에 영향을 주지 않는다.
2. 최적 부분 구조 (Optimal Substructure)
   : 부분 문제의 최적 결과가 전체에도 그대로 적용된다.

이러한 조건이 성립하지 않는 경우 그리디 알고리즘은 최적해를 구하지 못한다.

하지만, 이러한 경우에도 그리디 알고리즘은 근사 알고리즘으로 사용 가능하며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지 보장하려면 엄밀한 증명이 필요하다.

어떤 특별한 구조가 있는 문제에 대해서는 그리디 알고리즘이 언제나 최적해를 구할 수 있는데, 이러한 구조를 매트로이드라고 한다.