4.2.3 탐욕 알고리즘 이해하기
이 절의 내용을 살펴보기 전에 먼저 다음과 같은 두 가지 용어를 이해해야 합니다.
• 알고리즘 오버헤드(algorithmic overhead): 어떤 문제에 최적의 해결책을 찾기 위해서는 시간이 소요됩니다. 문제가 복잡해질수록 최적의 해결책을 찾는 데 걸리는 시간도 늘어납니다. 알고리즘 오버헤드를 Ωi로 표기하겠습니다.
• 최적해와의 차이(delta from optimal): 최적화 문제에는 최적의 해결책이 존재합니다. 이를 최적해(optimal solution)라고 부릅니다. 최적해가 무엇인지 알 수 없는 문제도 있습니다. 최적해를 계산하거나 검증하는 데 비현실적으로 오랜 시간이 소요되기 때문입니다. 최적해가 알려진 경우에는 우리가 가진 현재 해결책과 최적해와의 차이를 구할 수 있습니다. 이 책에서 설명하는 알고리즘은 보통 반복 과정을 통해 해결책을 점차 업데이트하는 방식을 취합니다. i번째 반복 단계의 해와 최적해 간의 차이를 Δi로 표기합니다.
복잡한 문제에는 다음과 같은 두 가지 전략을 사용할 수 있습니다.
• 전략 1: 시간을 들여 최적해에 가까운 해를 찾으려 노력합니다. 즉, Δi를 최소화합니다.
• 전략 2: 알고리즘 오버헤드 Ωi를 최소화합니다. 부족하지만 빠른 방법을 사용해서 최소한 동작하는 해결책을 찾아냅니다.
탐욕 알고리즘은 전략 2에 해당합니다. 즉, 전역적(global) 최적해를 찾으려 노력하는 대신, 알고리즘 오버헤드를 최소화하는 방식을 선택하는 것입니다.