알고리즘 - 그리디 알고리즘

그리디 (탐욕, 활동선택, 분수배낭)

DP가 모든 가능한 부분 문제를 풀어 비교한 뒤 최적해를 만든다면, 그리디(Greedy, 탐욕) 알고리즘은 매 순간 가장 좋아 보이는 선택을 즉시 결정하고 뒤를 돌아보지 않는다. 단순해 보이지만 이 단순함이 가장 큰 강점이자 함정이다. 어떤 문제는 그리디로 항상 최적이 보장되지만, 어떤 문제는 절대 최적이 보장되지 않는다. 본 글은 그리디의 정의·두 가지 조건·대표 응용·DP와의 차이를 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 16장). 제가 학교 알고리즘 과제에서 동전 거스름돈을 그리디로 풀어 한국 동전(500·100·50·10)에서는 항상 최적이 나오다가, 임의 동전(예: 4·3·1)에서는 최적이 깨지는 모습을 본 후로는 "그리디는 항상 최적이 아니라 특정 조건에서만 최적"이라는 사실을 손끝으로 받아들였다.

 

그리디 알고리즘의 두 가지 조건

그리디가 최적을 보장하기 위해서는 두 가지 핵심 조건이 동시에 성립해야 한다. 시험에서 자주 출제되는 항목이다.

조건	의미
그리디 선택 속성 (Greedy Choice Property)	현재 가장 좋아 보이는 선택이 전체 최적해의 일부가 될 수 있다
최적 부분 구조 (Optimal Substructure)	부분 문제의 최적해가 전체 최적해를 구성한다 (DP와 공유)

여기서 그리디 선택 속성이란 매 단계에서 지역적으로(locally) 최선의 선택을 했을 때 그것이 전역(global) 최적해의 일부가 됨이 증명되는 성질을 가리킨다. 두 조건이 모두 만족되면 그리디는 항상 최적해를 만들지만, 그리디 선택 속성이 깨지면 결과가 최적이 아닐 수 있다. 따라서 그리디를 사용할 때는 반드시 그리디 선택 속성을 증명하는 절차가 필요하다.

# 한국 동전 거스름돈 — 그리디 항상 최적 (500·100·50·10이 배수 관계)
def change_kr(amount):
    coins = [500, 100, 50, 10]
    used = []
    for c in coins:
        cnt, amount = divmod(amount, c)
        used.extend([c] * cnt)
    return used

print(change_kr(1230))   # [500, 500, 100, 100, 10, 10, 10] = 7개

# 임의 동전 — 그리디 최적 깨짐
def change_greedy(amount, coins):
    coins = sorted(coins, reverse=True)
    used = []
    for c in coins:
        cnt, amount = divmod(amount, c)
        used.extend([c] * cnt)
    return used

# 동전 [4, 3, 1]로 6을 만들기
print(change_greedy(6, [4, 3, 1]))   # [4, 1, 1] = 3개 (그리디)
# 최적은 [3, 3] = 2개!

위 예시가 그리디의 본질을 가장 잘 보여 준다. 한국 동전은 큰 단위가 작은 단위의 배수로 구성되어 그리디 선택 속성이 자연스럽게 성립하지만, [4, 3, 1] 같은 임의 동전은 그렇지 않아 그리디가 최적을 보장하지 못한다. 솔직히 제 경험상 학교 시험에서 가장 자주 함정으로 나오는 패턴이 정확히 이 동전 문제였고, "그리디는 증명 없이는 신뢰하지 말 것"이라는 한 줄을 외운 사람만 안정적으로 정답을 맞췄다.

그리디 vs DP — 언제 무엇을 쓸 것인가

그리디와 DP는 같은 "최적 부분 구조"를 공유하지만 결정적인 차이가 한 가지 있다. DP는 모든 부분 문제를 풀어 비교하고, 그리디는 한 가지만 선택해 다음 단계로 넘어간다.

비교 항목	그리디	DP
선택 방식	한 가지 선택 (지역 최적)	모든 선택 비교 (전역 최적)
시간복잡도	일반적으로 O(n log n)	일반적으로 O(n²)~O(nW)
최적해 보장	그리디 선택 속성 성립 시만	항상 보장
메모리	O(1) 또는 O(n)	상태 공간 크기만큼
적합한 상황	큰 입력·단순 결정	작은~중간 입력·복잡한 의존성
대표 예시	활동 선택·허프만·MST	0-1 배낭·LCS·편집 거리

여기서 가장 헷갈리는 짝이 분수 배낭(Fractional Knapsack)과 0-1 배낭(0-1 Knapsack)이다. 분수 배낭은 물건을 쪼개 담을 수 있는 변형으로 그리디로 항상 최적이지만, 0-1 배낭은 통째로만 담아야 해서 반드시 DP가 필요하다. 두 문제의 차이가 그리디 적용 가능성을 가르는 가장 표준적인 예시이다.

# 분수 배낭 — 그리디로 항상 최적
def fractional_knapsack(items, capacity):
    # items: [(value, weight), ...]
    items.sort(key=lambda x: x[0] / x[1], reverse=True)  # 단위 무게당 가치 기준 정렬
    total = 0
    for value, weight in items:
        if capacity >= weight:
            total += value
            capacity -= weight
        else:
            total += value * (capacity / weight)         # 쪼개서 담음
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))   # 240

여기서 단위 무게당 가치(value/weight) 기준 정렬이 분수 배낭의 그리디 선택 속성이며, 이 한 줄로 분수 배낭이 항상 최적이 됨을 수학적으로 증명할 수 있다.

대표 그리디 응용 — 활동 선택·허프만·MST

그리디가 항상 최적을 보장하는 대표 문제 세 가지를 정리한다.

활동 선택 문제(Activity Selection)는 시작·종료 시각이 정해진 활동들 중에서 서로 겹치지 않는 최대 개수의 활동을 선택하는 문제이다. 그리디 전략은 단순하다. 종료 시각이 빠른 순으로 정렬하고, 직전 선택과 겹치지 않으면 선택한다. 이 단순한 전략이 항상 최적임을 교환 논증으로 증명할 수 있다.

def activity_selection(activities):
    # activities: [(start, end), ...]
    activities.sort(key=lambda a: a[1])    # 종료 시각 오름차순
    selected = []
    last_end = -1
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10)]
print(activity_selection(acts))
# [(1, 4), (5, 7)] — 또는 종료 빠른 다른 조합

허프만 코딩(Huffman Coding)은 1952년 데이비드 허프만이 제안한 무손실 압축 알고리즘으로, 자주 등장하는 문자에 짧은 비트열을 부여해 평균 부호 길이를 최소화한다. 그리디 전략은 빈도가 가장 낮은 두 노드를 매번 골라 부모로 묶는 방식이며, 우선순위 큐(최소 힙)로 구현해 O(n log n)에 끝난다. ZIP·gzip·JPEG·MP3 같은 거의 모든 압축 형식의 한 단계가 허프만 코딩이라는 점에서 그리디의 실전 채택을 가장 잘 보여 주는 예시이다(출처: 위키백과 — Huffman coding).

최소 신장 트리(MST, Minimum Spanning Tree)는 가중치 그래프에서 모든 정점을 연결하면서 간선 가중치 합이 최소가 되는 부분 트리를 찾는 문제이다. 두 가지 대표 그리디 알고리즘이 있다.

알고리즘	전략	시간복잡도
Kruskal	모든 간선을 가중치 오름차순 정렬 후, 사이클을 만들지 않는 간선부터 선택	O(E log E)
Prim	한 정점에서 시작해 매번 트리에 가장 가까운 정점을 추가	O(E log V)

Kruskal은 Union-Find 자료구조로 사이클 검사를 효율화하고, Prim은 우선순위 큐로 최소 가중치 간선을 빠르게 꺼낸다. 두 알고리즘 모두 그리디 선택 속성이 cut property로 증명되며, 통신망·도로망·전력망 설계의 표준 도구이다.

마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "그리디는 매 단계에서 지역적으로 최선의 선택을 하는 알고리즘 패러다임으로, 그리디 선택 속성과 최적 부분 구조가 동시에 성립할 때만 전역 최적을 보장한다. 활동 선택·허프만 코딩·MST(Kruskal·Prim)·분수 배낭이 대표 응용이며, 0-1 배낭처럼 그리디 선택 속성이 깨지는 문제는 DP가 필요하다"는 두 문장이 표준 답안 표현으로 통한다. 알고리즘 시리즈는 이제 분할 정복·DP·그리디 세 패러다임을 채웠으며, 다음으로는 백트래킹·그래프 알고리즘·최단 경로 같은 후속 영역으로 10편 시리즈를 마무리해 갈 예정이다.

---

메타 디스크립션: 그리디 알고리즘의 두 조건(그리디 선택 속성·최적 부분 구조), DP와의 차이, 활동 선택·허프만 코딩·MST(Kruskal·Prim)·분수 배낭 같은 고전 응용을 알고리즘 입문자 관점에서 세심하게 정리합니다.