탐욕 알고리즘

탐욕 알고리즘(greedy algorithm)은 문제를 해결하는 각 단계에서 현재 상태를 기준으로 가장 유리하다고 판단되는 선택을 수행하여 전체 해를 구성하는 알고리즘 설계 기법이다. 일반적으로 이미 내린 선택을 다시 검토하지 않으며, 하나의 선택이 이루어지면 그 선택으로 인해 남은 부분 문제를 계속 해결한다.^[1]

탐욕 알고리즘의 핵심은 단순히 매 순간 가장 큰 값이나 가장 작은 값을 고르는 데 있지 않다. 문제의 구조에 맞는 탐욕 선택 기준을 정의하고, 그 기준에 따른 선택을 포함하는 최적해가 항상 존재한다는 사실을 증명해야 한다. 같은 문제에서도 시작 시간이 빠른 항목, 종료 시간이 빠른 항목, 비용이 낮은 항목처럼 여러 선택 기준을 만들 수 있지만, 이 가운데 일부만 전체 최적해를 보장할 수 있다.

탐욕 알고리즘이 정확한 최적해를 구하려면 일반적으로 탐욕 선택 속성과 최적 부분 구조가 필요하다. 탐욕 선택 속성은 현재 단계의 국소적으로 최적인 선택을 포함하는 전체 최적해가 존재한다는 성질이며, 최적 부분 구조는 전체 최적해가 선택 이후 남은 부분 문제의 최적해를 포함한다는 성질이다.^[2]

탐욕 알고리즘은 정렬이나 우선순위 큐, 서로소 집합 자료구조 등과 결합되는 경우가 많다. 활동 선택 문제에서는 종료 시간이 가장 빠른 활동부터 선택하고, 크루스칼 알고리즘에서는 가중치가 가장 작은 간선을 차례로 검사하며, 다익스트라 알고리즘에서는 현재까지의 거리가 가장 짧은 정점을 확정한다. 각 알고리즘은 국소적인 선택을 반복하지만, 선택 기준과 정확성 증명은 서로 다르다.

탐욕적 선택이 항상 최적해를 만드는 것은 아니다. 예를 들어 일반적인 0-1 배낭 문제에서는 단위 무게당 가치가 높은 물건부터 고르는 방식이 최적해를 놓칠 수 있다. 반면 물건을 일부만 나누어 담을 수 있는 분할 가능 배낭 문제에서는 같은 선택 기준으로 최적해를 구할 수 있다. 따라서 탐욕 알고리즘의 적용 여부는 구현 형태가 아니라 문제의 수학적 구조와 증명을 통해 판단한다.