알고리즘 - 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
- 위키피디아

자료 1) 탐욕 알고리즘 예시 (그림자료출처)

• 위의 자료를 보면, 이진트리에서 매 순간 최대값을 구하여 도출 한 최대값 결과는 12지만 실제 최대값은 99임을 알 수 있다.

탐욕 알고리즘의 조건

• 탐욕스런 선택 조건(greedy choice property)

  앞의 선택이 이후의 선택에 영향을 주지 않는다는 것

• 최적 부분 구조 조건(optimal substructure)

  문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것

위의 두가지 조건이 만족되지 않는다면 탐욕 알고리즘은 최적해를 구하지 못한다.

그러나

1. 근사 알고리즘으로 사용이 가능하다
2. 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용 가능하다