그리디 알고리즘

그리디(Greedy, 탐욕법) 알고리즘은 여러 경우 중 하나를 골라야 할 때마다 그 순간 가장 좋아 보이는 선택을 하며 최종 해답에 도달하는 방법이다. 앞으로의 선택이나 지나간 선택을 다시 고려하지 않는다. 구현이 간단하고 빠르지만, 최적해를 항상 보장하지는 않는다.

문제를 푸는 세 단계

선택 절차(Selection Procedure): 현재 상태에서 가장 좋은 선택을 한다.
적절성 검사(Feasibility Check): 그 선택이 문제의 조건을 만족하는지 검사한다.
해답 검사(Solution Check): 원래 문제가 해결되었는지 확인하고, 아니라면 1로 돌아간다.

예시: 거스름돈

4,040원짜리 물건을 사고 5,000원을 냈다. 거스름돈 960원을 동전 개수가 최소가 되도록 주려면?

선택: 지금 쓸 수 있는 가장 큰 동전을 고른다.
적절성 검사: 고른 동전까지 합한 금액이 거슬러 줄 금액을 넘으면, 그 동전을 빼고 한 단계 작은 동전을 고른다.
해답 검사: 합이 960원이 되었는지 확인하고, 부족하면 반복한다.

결과: 500원 1개 → 100원 4개 → 50원 1개 → 10원 1개, 총 7개

def min_coins(amount, coins=(500, 100, 50, 10)):
    count = 0
    for coin in coins:          # 큰 동전부터
        count += amount // coin
        amount %= coin
    return count
 
print(min_coins(960))  # 7

왜 이 경우에는 그리디가 맞을까

500, 100, 50, 10원처럼 큰 동전이 항상 작은 동전의 배수인 화폐 체계에서는, 큰 동전 하나를 작은 동전 여러 개로 바꾸면 개수만 늘어난다. 그래서 큰 것부터 고르는 그리디가 최적이다.

하지만 동전이 {500, 400, 100}이고 800원을 거슬러야 한다면, 그리디는 500 + 100 × 3 = 4개를 고르지만 최적은 400 × 2 = 2개다. 이런 경우에는 동적 계획법으로 풀어야 한다.

예시: 로마 숫자로 바꾸기

1~3999의 수를 로마 숫자로 바꾸는 것도 큰 값부터 고르는 그리디다. 빼기 표기(4 = IV, 9 = IX, 40 = XL, 90 = XC, 400 = CD, 900 = CM) 여섯 개를 값 표에 함께 넣으면 「남은 수 이하인 가장 큰 값」을 반복해서 고르기만 하면 된다.

TABLE = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'), (90, 'XC'),
         (50, 'L'), (40, 'XL'), (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')]
 
def to_roman(n):
    out = []
    for value, sym in TABLE:
        count, n = divmod(n, value)     # 이 값을 몇 번 쓸 수 있나
        out.append(sym * count)
    return ''.join(out)
 
print(to_roman(944))   # CMXLIV

표의 크기가 고정이라 O(1)이다. 이 그리디가 맞는 이유는 로마 숫자가 사실상 자리마다 독립된 십진 표기이기 때문이다. 백의 자리 9는 늘 CM, 십의 자리 4는 늘 XL이라, 큰 값부터 고르면 자리별 표기가 그대로 나온다. 거꾸로 로마 숫자를 수로 바꿀 때는 왼쪽부터 읽으며 다음 글자보다 작은 글자는 빼고 나머지는 더한다(IV = -1 + 5).

그리디의 한계와 정당성 확인

그리디는 부분적인 최적해들을 모은 것이 곧 전체 문제의 최적해가 될 때만 쓸 수 있다. 이 조건은 두 성질로 나눠 확인한다.

성질	질문
탐욕 선택 속성(greedy choice property)	이번 단계에서 고른 선택을 포함하는 최적해가 항상 존재하는가
최적 부분 구조(optimal substructure)	그 선택을 한 뒤 남은 부분 문제의 최적해를 더하면 전체 최적해가 되는가

최적 부분 구조는 DP도 요구하는 성질이다. 그리디는 여기에 탐욕 선택 속성이 더해져 되돌아볼 필요가 없을 때 쓴다. 증명은 보통 「최적해가 내 선택을 안 했다면, 그 자리를 내 선택으로 바꿔도 나빠지지 않는다」는 교환 논증(exchange argument)으로 한다.

그리디가 늘 통하는 구조: 매트로이드

교환 논증이 문제마다 따로 필요 없는 경우가 있다. 고를 수 있는 원소 집합 S와 「같이 골라도 되는」 부분집합의 모음 I(독립 집합)가 다음 두 성질을 가지면 매트로이드(matroid) 라고 한다.

성질	뜻
유전성(hereditary)	독립 집합의 부분집합도 독립이다. 공집합은 독립이다
교환성(exchange)	독립 집합 A, B에서 \|A\| < \|B\|이면, B에만 있는 원소 x 중 A ∪ {x}가 여전히 독립인 것이 있다

원소마다 양의 가중치가 있을 때 무거운 순으로 보면서, 넣어도 독립이면 넣는 그리디는 매트로이드에서 항상 가중치 합이 최대인 독립 집합을 찾는다.

A ← ∅
가중치 내림차순으로 x를 하나씩 본다:
    A ∪ {x}가 독립이면 A ← A ∪ {x}

그래프의 간선 집합에서 「사이클이 없는 간선 모음(숲)」을 독립으로 보면 매트로이드가 된다(그래픽 매트로이드). 가중치를 뒤집어 가벼운 순으로 같은 그리디를 돌린 것이 크루스칼 알고리즘이고, 「넣어도 독립인가」 검사를 서로소 집합이 맡는다. 반대로 0-1 배낭 문제는 교환성이 깨져 그리디가 실패한다.

그래서 그리디로 풀 때는

이 선택 기준이 왜 항상 최적인지 짧게라도 논리적으로 확인하고,
반례가 떠오르면 완전 탐색이나 DP로 방향을 바꾼다.
최적해를 포기하고 빠른 근사해가 필요할 때(집합 덮개, 외판원 문제의 휴리스틱)도 그리디를 쓴다. 이때는 「최적」이 아니라 「얼마나 가까운가」를 따진다.

그리디가 정당한 대표 문제로는 회의실 배정(끝나는 시간이 빠른 순), 최소 신장 트리(크루스칼·프림), 다익스트라 최단 경로 등이 있다. 정렬과 함께 쓰이는 경우가 많다.

핵심 정리

그리디 = 매 순간 최선의 선택, 되돌아보지 않음
빠르고 간단하지만 최적해를 보장하지 않는다.
선택 기준이 정당한지(반례가 없는지) 확인하는 것이 핵심

관련 노트: 동적 계획법, 다익스트라, 서로소 집합(크루스칼), 스위핑

버그 제보