IT용어위키

그리디 알고리즘(Greedy Algorithm)은 현재 단계에서 최적이라고 생각되는 선택을 반복하여 전체 문제의 최적해를 구하는 알고리즘이다. 탐욕적 기법을 사용하여 복잡한 문제를 빠르게 해결할 수 있지만, 항상 최적해를 보장하지는 않는다.

개요

그리디 알고리즘은 다음과 같은 특징을 가진 문제에 적합하다.

탐욕적 선택 속성(Greedy Choice Property)
- 현재 단계에서 최적의 선택을 하면, 이후 단계에서도 최적해를 유지할 수 있는 경우.
최적 부분 구조(Optimal Substructure)
- 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구할 수 있는 경우.

그리디 알고리즘의 종류

그리디 알고리즘은 다양한 방식으로 적용될 수 있으며, 대표적인 기법은 다음과 같다.

정렬 기반 선택(Selection by Sorting)
- 아이템을 특정 기준으로 정렬한 후, 순차적으로 선택하는 방식.
우선순위 큐(Priority Queue)
- 가장 우선순위가 높은 요소를 먼저 처리하는 방식.

대표적인 그리디 알고리즘 문제

그리디 알고리즘은 다양한 최적화 문제에서 활용된다.

동전 교환 문제(Coin Change Problem)
- 최소한의 동전 개수로 특정 금액을 만드는 문제.
배낭 문제(Knapsack Problem, 분할 가능)
- 무게 대비 가치가 높은 물건을 먼저 선택하여 최대 이익을 얻는 문제.
최소 신장 트리(Minimum Spanning Tree, MST)
- 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)에서 활용됨.
활동 선택 문제(Activity Selection Problem)
- 겹치지 않는 최대 개수의 활동을 선택하는 문제.
허프만 코딩(Huffman Coding)
- 최적의 압축을 위해 가중치를 기준으로 트리를 구성하는 문제.

동작 원리

그리디 알고리즘은 다음과 같은 방식으로 동작한다.

문제를 구성하는 요소를 특정 기준으로 정렬.
현재 단계에서 가장 최적이라고 판단되는 선택 수행.
해당 선택이 전체 문제를 해결할 때까지 반복.

예제 문제

대표적인 예제 중 하나는 동전 교환 문제(Coin Change Problem)이다.

예제 1: 동전 교환 문제

주어진 동전 단위로 특정 금액을 만들 때, 최소 개수의 동전을 사용하는 문제.

코드

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 큰 동전부터 정렬
    num_coins = 0
    for coin in coins:
        if amount == 0:
            break
        count = amount // coin
        num_coins += count
        amount -= count * coin
    return num_coins if amount == 0 else -1  # 거슬러 줄 수 없는 경우 -1 반환

# 예제 실행
coins = [1, 5, 10, 25]
amount = 63
print(coin_change_greedy(coins, amount))

출력 결과 예시:
6 (25x2 + 10x1 + 5x0 + 1x3)

- 주의:** 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우도 있다. 예를 들어, 동전 단위가 [1, 3, 4]이고 6원을 만들 때, 그리디 알고리즘은 4+1+1(3개)로 선택하지만 최적해는 3+3(2개)이다.

예제 2: 분할 가능 배낭 문제(Fractional Knapsack)

배낭의 용량이 제한되어 있을 때, 가치를 최대화하도록 아이템을 선택하는 문제.

코드

def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0

    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

# 예제 실행
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(fractional_knapsack(weights, values, capacity))

출력 결과 예시:
7.5

시간 복잡도

그리디 알고리즘의 시간 복잡도는 일반적으로 정렬 이후 선택을 수행하므로 **O(n log n)**이다.

동전 교환 문제: **O(n log n)**
분할 가능 배낭 문제: **O(n log n)**
최소 신장 트리(MST) (크루스칼 알고리즘): **O(E log E)**
활동 선택 문제: **O(n log n)**

한계

그리디 알고리즘은 모든 문제에서 최적해를 보장하지 않는다.

최적 부분 구조가 없는 경우
- 그리디 선택이 이후 단계에서 잘못된 선택이 될 수 있음.
전체 탐색이 필요한 경우
- 일부 문제에서는 다이나믹 프로그래밍(DP) 또는 완전 탐색(Brute Force)이 필요함.

예를 들어, 0/1 배낭 문제에서는 그리디 알고리즘이 최적해를 보장하지 않으므로 동적 계획법을 사용해야 한다.

응용

그리디 알고리즘은 다양한 분야에서 활용된다.

네트워크 설계
- 최소 비용으로 모든 노드를 연결 (MST)
데이터 압축
- 허프만 코딩을 통한 최적 압축
일정 최적화
- 가장 많은 작업을 수행하는 스케줄링

같이 보기

참고 문헌

Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
Kleinberg, Jon, and Eva Tardos. "Algorithm Design." Pearson, 2005.