CS학습2026년 8월 24일

Greedy: 매 순간 최선의 선택이 전체 최적해가 되는 조건

그리디(Greedy) 알고리즘은 매 단계에서 지금 당장 가장 좋아 보이는 선택을 하고 다시 되돌아보지 않는 방식이다. 항상 최적해를 보장하지는 않지만, 문제가 탐욕적 선택 속성과 최적 부분 구조를 만족할 때는 동적 계획법(DP)보다 훨씬 빠르고 단순하게 최적해를 구할 수 있다. 이 글에서는 그리디가 통하는 조건을 원리 수준에서 살펴보고, 대표 문제인 활동

송민성6분 읽기

1. 개념

그리디(Greedy) 알고리즘은 문제를 여러 단계로 나눈 뒤, 각 단계에서 현재 시점 기준으로 가장 좋아 보이는 선택지를 즉시 선택하고 이후 단계로 넘어가는 방식이다. 한 번 내린 선택은 번복하지 않는다.

핵심은 "국소적으로 최선의 선택(local optimum)을 반복하면 전역적으로 최선의 결과(global optimum)에 도달한다"는 가정이다. 이 가정이 수학적으로 성립하는 문제에서만 그리디를 적용해 정확한 답을 얻을 수 있다.

2. 왜 사용하는가

동적 계획법(DP)은 부분 문제의 답을 모두 계산하고 저장해서 최적해를 보장하지만, 상태 공간이 커지면 시간복잡도와 메모리 사용량이 함께 늘어난다. 그리디는 조건만 만족하면 매 단계 O(1)~O(log n) 수준의 선택만으로 문제를 풀 수 있어 DP보다 압도적으로 빠르다.

예를 들어 활동 선택 문제(Activity Selection Problem)를 DP로 풀면 O(n²)이 걸리지만, 그리디로 풀면 정렬 비용을 포함해도 O(n log n)에 끝난다.

3. 동작 원리

그리디가 정확한 답을 보장하려면 다음 두 조건을 모두 만족해야 한다.

탐욕적 선택 속성(Greedy Choice Property) 전역 최적해를 구성하는 과정에서, 지금 단계의 탐욕적 선택이 이후에도 항상 최적해의 일부로 남을 수 있다는 성질이다. 즉 현재 선택을 나중에 후회하고 바꿀 필요가 없어야 한다.

최적 부분 구조(Optimal Substructure) 전체 문제의 최적해가 부분 문제의 최적해로 구성된다는 성질이다. 이는 DP와 그리디가 공유하는 조건이지만, 그리디는 여기에 탐욕적 선택 속성까지 추가로 요구한다.

두 조건 중 하나라도 깨지면 그리디는 틀린 답을 낼 수 있다. 대표적으로 0/1 배낭 문제(0/1 Knapsack)는 최적 부분 구조는 있지만 탐욕적 선택 속성이 없어서 그리디로 풀면 최적해를 보장하지 못하고, 분할 가능 배낭 문제(Fractional Knapsack)는 두 조건을 모두 만족해서 그리디로 정확히 풀 수 있다.

증명 방식은 보통 "교환 논증(Exchange Argument)"을 쓴다. 임의의 최적해가 있다고 가정하고, 그 해를 그리디 선택으로 바꿔도 결과가 나빠지지 않음을 보여서 그리디 선택이 항상 최적해에 포함될 수 있음을 증명한다.

4. 코드 예제

4-1. 활동 선택 문제 (그리디가 성립하는 대표 사례)

회의실 하나에서 겹치지 않게 최대한 많은 활동을 진행하려 할 때, "종료 시간이 가장 빠른 활동부터 선택한다"는 그리디 전략이 최적해를 보장한다.

python

def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    # activities: (시작 시간, 종료 시간) 튜플 리스트
    # 종료 시간 기준 오름차순 정렬 - O(n log n)
    sorted_activities = sorted(activities, key=lambda x: x[1])

    selected = [sorted_activities[0]]
    last_end_time = sorted_activities[0][1]

    for start, end in sorted_activities[1:]:
        if start >= last_end_time:  # 이전 활동과 겹치지 않으면 선택
            selected.append((start, end))
            last_end_time = end

    return selected


activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(result)  # [(1, 4), (5, 7), (8, 11), (12, 16)]
print(len(result))  # 4

4-2. 거스름돈 문제 (그리디가 조건부로만 성립하는 사례)

동전 단위가 1, 5, 10, 50처럼 배수 관계로 잘 짜여 있으면 그리디로 최소 동전 개수를 구할 수 있지만, 임의의 동전 단위에서는 실패할 수 있다.

python

def min_coins_greedy(coins: list[int], amount: int) -> list[int]:
    # coins는 내림차순 정렬되어 있어야 한다
    coins = sorted(coins, reverse=True)
    result = []
    remaining = amount

    for coin in coins:
        count = remaining // coin
        if count > 0:
            result.extend([coin] * count)
            remaining -= coin * count

    if remaining != 0:
        raise ValueError("주어진 동전으로 정확히 거스름돈을 만들 수 없습니다")

    return result


# 성립하는 경우: 한국 동전 체계
print(min_coins_greedy([500, 100, 50, 10], 730))
# [500, 100, 100, 10, 10, 10]

# 실패하는 경우: 임의의 동전 단위 (1, 3, 4로 6원 만들기)
# 그리디는 4 + 1 + 1 = 3개를 선택하지만 실제 최적해는 3 + 3 = 2개
print(min_coins_greedy([4, 3, 1], 6))
# [4, 1, 1] - 최적해가 아님 (정답은 [3, 3])

이 실패 사례가 바로 그리디를 적용하기 전에 반드시 "탐욕적 선택 속성이 성립하는가"를 증명해야 하는 이유다. 동전 문제는 동전 단위가 일반적인 경우 DP(O(n × amount))로 풀어야 정확한 최소 개수를 보장한다.

5. 시간 복잡도 또는 성능 특성

| 문제 | 그리디 시간복잡도 | DP 시간복잡도 | |---|---|---| | 활동 선택 문제 | O(n log n) (정렬 비용) | O(n²) | | 분할 가능 배낭 문제 | O(n log n) (정렬 비용) | 해당 없음 (그리디 전용) | | 최소 신장 트리 (Kruskal) | O(E log E) | 해당 없음 | | 거스름돈 (표준 동전 체계) | O(k), k는 동전 종류 수 | O(n × amount) | | 0/1 배낭 문제 | 그리디 불가 (오답 가능) | O(n × capacity) |

그리디는 대부분 정렬이나 우선순위 큐(Priority Queue) 구성 비용이 지배적이며, 선택 자체는 선형 시간에 끝나는 경우가 많다.

6. 실무 사용 사례

Kruskal / Prim 알고리즘 (최소 신장 트리) 네트워크 설계에서 모든 노드를 최소 비용으로 연결할 때 사용한다. 간선을 비용 순으로 정렬한 뒤 사이클을 만들지 않는 간선을 그리디하게 선택한다.

Huffman 코딩 (데이터 압축) 문자 등장 빈도를 기반으로 가장 빈도가 낮은 두 노드를 반복해서 병합하는 그리디 전략으로 최적의 접두사 코드(Prefix Code)를 생성한다. ZIP, JPEG 등 압축 포맷의 기반 기술이다.

Dijkstra 최단 경로 알고리즘 매 단계에서 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 그리디하게 선택한다. 단, 음수 가중치가 있으면 탐욕적 선택 속성이 깨져서 정확한 답을 보장하지 못한다.

작업 스케줄링 / 캐시 교체 정책 운영체제의 SJF(Shortest Job First) 스케줄링이나 캐시의 LFU(Least Frequently Used) 같은 정책도 넓게 보면 그리디 전략의 일종이다.

7. 주의할 점

그리디가 통하는지 증명 없이 적용하지 않는다 "직관적으로 맞아 보인다"는 근거로 그리디를 적용하면 안 된다. 탐욕적 선택 속성과 최적 부분 구조를 반례를 찾아보거나 교환 논증으로 검증한 뒤 적용해야 한다.

한 번 내린 선택은 되돌릴 수 없다 그리디는 백트래킹(Backtracking)을 하지 않는다. 선택 기준을 잘못 세우면 전체 결과가 틀어져도 복구할 방법이 없다.

정렬 기준 선택이 정답 여부를 좌우한다 활동 선택 문제에서 "시작 시간이 빠른 순"으로 정렬하면 틀린 답이 나오고, "종료 시간이 빠른 순"으로 정렬해야 정답이 나온다. 어떤 기준으로 정렬할지가 그리디 설계의 핵심이다.

DP와 헷갈리지 않는다 0/1 배낭 문제처럼 최적 부분 구조는 있지만 탐욕적 선택 속성이 없는 문제에 그리디를 적용하면 그럴듯한 오답을 만들어낸다. 이런 문제는 반드시 DP로 풀어야 한다.

8. 핵심 정리

그리디는 매 단계에서 되돌아보지 않고 국소 최적 선택을 반복하는 알고리즘 설계 기법이다. 탐욕적 선택 속성과 최적 부분 구조를 모두 만족하는 문제에서만 정확한 최적해를 보장하며, 이 조건이 성립하면 DP보다 훨씬 빠르고 간결한 해법을 제공한다. 활동 선택 문제, 최소 신장 트리, 허프만 코딩처럼 그리디가 검증된 문제와, 0/1 배낭 문제처럼 그리디가 실패하는 문제를 구분하는 능력이 실무 적용의 핵심이다.