그리디 알고리즘: 탐욕적 선택의 정당성과 실전 전략

알고리즘 설계의 세계에서 가장 직관적이면서도 강력한 기법을 꼽으라면 단연 그리디(Greedy) 알고리즘을 들 수 있습니다. '탐욕 알고리즘'이라고도 불리는 이 방식은 미래를 계산하거나 과거를 돌아보지 않고, 오직 '현재 이 순간'에서 가장 최선이라고 판단되는 해답을 선택해 나가는 전략입니다. 구현이 매우 간단하고 실행 속도가 압도적이라는 장점이 있지만, 모든 상황에서 정답을 보장하지는 않는다는 위험한 속성도 함께 지니고 있습니다. 본 포스팅에서는 그리디 알고리즘이 언제 마법 같은 해답이 되는지, 그리고 어떤 함정이 숨어 있는지 2,500자 이상의 상세한 분석으로 파헤쳐 보겠습니다.

1. 그리디 알고리즘의 철학과 동작 원리

그리디 알고리즘의 핵심 철학은 '지역 최적해(Local Optimum)의 집합이 전역 최적해(Global Optimum)가 될 것이다'라는 믿음입니다. 우리는 보통 어떤 문제를 해결할 때 수많은 경우의 수를 따지며 고민하지만, 그리디는 그 고민을 생략합니다. 매 단계에서 가장 이득이 되는 선택을 하고, 그 선택을 절대로 번복하지 않습니다. 이러한 단순함 덕분에 그리디 알고리즘은 복잡한 점화식이나 상태 테이블 없이도 매우 빠른 시간 복잡도 내에 문제를 해결합니다.

1-1. 탐욕적 선택이 정답이 되기 위한 필수 과정

단순히 당장 좋은 것을 고른다고 해서 다 정답이 되는 것은 아닙니다. 그리디 알고리즘이 유효하게 작동하려면 다음의 두 가지 수학적 조건이 충족되어야 합니다. 이 조건이 깨진다면 그리디는 최적해를 찾지 못하고 엉뚱한 길로 빠지게 됩니다.

탐욕적 선택 속성(Greedy Choice Property): 이전의 선택이 이후의 선택에 영향을 주지 않으며, 각 단계의 최선의 선택이 결국 전체 문제의 최적해를 구성한다는 성질입니다.
최적 부분 구조(Optimal Substructure): 문제의 전체 최적해가 부분 문제들의 최적해들로부터 도달할 수 있는 구조여야 합니다.

2. 그리디 알고리즘이 빛을 발하는 실전 사례

그리디가 완벽하게 동작하는 가장 고전적인 예시는 거스름돈 문제와 회의실 배정 문제입니다. 특히 화폐 단위가 서로 배수 관계(500원, 100원, 50원 등)를 이룰 때, 큰 단위부터 거슬러 주는 방식은 항상 동전의 개수를 최소화합니다. 이는 큰 동전 하나를 쓰는 것이 작은 동전 여러 개를 쓰는 것보다 무조건 유리하다는 논리적 정당성이 확보되기 때문입니다.

2-1. 활동 선택 문제(Activity Selection)와 정렬의 중요성

회의실 배정 문제와 같은 활동 선택 문제에서 그리디는 '종료 시간'이라는 명확한 기준을 제시합니다. 회의가 일찍 끝나야 다음 회의를 시작할 수 있는 여유가 많아진다는 직관은, 종료 시간 기준의 오름차순 정렬을 통해 전역 최적해로 연결됩니다. 여기서 알 수 있듯이, 그리디 알고리즘의 성능과 정답 여부는 '어떤 기준으로 정렬하여 탐욕적 선택을 내릴 것인가'에 달려 있습니다.

3. 그리디의 한계와 정당성 증명 방법

그리디는 모든 경로를 탐색하지 않기에, 특정 조건에서는 무력해집니다. 대표적인 것이 0-1 배낭 문제입니다. 무게당 가치가 높은 물건부터 담는 그리디 전략은, 무게 제한 때문에 더 가치 있는 물건들의 조합을 놓치게 만듭니다. 이럴 때는 동적 계획법(DP)이 대안이 됩니다. 따라서 그리디를 적용하기 전에는 반드시 반례(Counter-example)를 고민해야 합니다.

3-1. 교체 증명법(Exchange Argument)

내가 세운 그리디 전략이 맞는지 증명하는 가장 강력한 방법은 '교체 증명법'입니다. 임의의 최적해가 있다고 가정하고, 그 해의 일부분을 나의 탐욕적 선택으로 바꾸었을 때 결과가 나빠지지 않음을 증명하는 방식입니다. 이 과정은 알고리즘의 신뢰도를 높여주며 기술 면접에서도 매우 중요하게 평가받는 역량입니다.

4. 복잡도 분석 및 실무적 가치

대부분의 그리디 알고리즘은 데이터를 정렬하는 데 가장 많은 시간을 소요합니다. 따라서 시간 복잡도는 주로 $O(N \log N)$이 되며, 이후의 선택 과정은 $O(N)$으로 매우 빠릅니다. 실무에서는 데이터 압축을 위한 허프만 코딩(Huffman Coding), 네트워크 최단 경로를 찾는 다익스트라 알고리즘, 최소 비용 신장 트리를 구하는 크루스칼 알고리즘 등에서 그리디의 원리가 핵심적으로 작동합니다.


# 거스름돈 문제 그리디 구현 (Python)
def change_coins(money, coins):
    coins.sort(reverse=True) # 큰 동전부터 확인
    count = 0
    for coin in coins:
        count += money // coin
        money %= coin
    return count

[그리디 알고리즘 핵심 요약]
1. 원리: 매 단계에서 현재 시점의 최선책을 선택하여 전역 최적해를 노립니다.
2. 정당성: 탐욕적 선택 속성과 최적 부분 구조가 보장될 때만 정답을 도출할 수 있습니다.
3. 실무: 정렬과 결합하여 매우 빠른 속도를 자랑하며, 다양한 경로 최적화 로직의 기반이 됩니다.

tech-korea