그리디 알고리즘 (Greedy Algorithm): 순간 최선의 선택

프로그래밍에서 가장 직관적이고 우아한 알고리즘 중 하나가 바로 **그리디 알고리즘(Greedy Algorithm)**입니다. 말 그대로 “욕심쟁이”처럼 매 순간 최선의 선택을 하는 방식입니다. 이번 글에서는 그리디 알고리즘의 원리와 한계, 그리고 대표적인 문제들을 알아보겠습니다.

1. 그리디 알고리즘의 기초 개념

그리디 알고리즘의 정의

각 단계에서 순간적으로 최선의 선택을 하는 알고리즘입니다. 미래를 내다보지 않고 현재 상황에서 가장 좋은 선택을 반복합니다.

그리디 알고리즘의 특징

1. 단순함: 구현이 간단하고 직관적
2. 효율성: 일반적으로 빠른 실행 시간
3. 근시안적: 미래 결과를 고려하지 않음

그리디 vs 동적 계획법

• 그리디: 한 번의 선택으로 끝 (결정론적)
• 동적 계획법: 모든 가능성을 고려 (완전 탐색)

2. 그리디 알고리즘의 작동 원리

최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 합니다.

그리디 선택 속성 (Greedy Choice Property)

지역적 최적 선택이 전역적 최적해로 이어져야 합니다.

예시: 동전 거스름돈

동전: [1, 5, 10, 25]원
거스름돈: 36원

그리디 선택:
25원 → 1개 (남은 금액: 11원)
10원 → 1개 (남은 금액: 1원)
1원 → 1개 (남은 금액: 0원)

결과: 3개의 동전

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

1. 활동 선택 문제 (Activity Selection Problem)

문제: 겹치지 않는 최대 개수의 활동을 선택하세요.

def activity_selection(activities):
    """
    활동 선택 문제 해결 (그리디 알고리즘)

    Args:
        activities (list): [(시작시간, 종료시간), ...] 형태의 활동 리스트

    Returns:
        list: 선택된 활동들의 인덱스
    """
    # 종료 시간을 기준으로 정렬
    activities.sort(key=lambda x: x[1])

    selected = [0]  # 첫 번째 활동 선택
    last_end_time = activities[0][1]

    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:
            selected.append(i)
            last_end_time = activities[i][1]

    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)]
selected_indices = activity_selection(activities)

print("선택된 활동들:")
for idx in selected_indices:
    start, end = activities[idx]
    print(f"활동 {idx}: {start}시 - {end}시")

2. 허프만 코딩 (Huffman Coding)

문제: 문자의 빈도에 따라 최적의 이진 코드를 생성하세요.

import heapq
from collections import defaultdict

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    """
    허프만 트리 구축

    Args:
        text (str): 압축할 텍스트

    Returns:
        HuffmanNode: 허프만 트리의 루트
    """
    # 빈도 계산
    freq = defaultdict(int)
    for char in text:
        freq[char] += 1

    # 우선순위 큐 생성
    pq = [HuffmanNode(char, count) for char, count in freq.items()]
    heapq.heapify(pq)

    # 허프만 트리 구축
    while len(pq) > 1:
        # 빈도가 가장 작은 두 노드 추출
        left = heapq.heappop(pq)
        right = heapq.heappop(pq)

        # 새로운 내부 노드 생성
        internal = HuffmanNode(None, left.freq + right.freq)
        internal.left = left
        internal.right = right

        heapq.heappush(pq, internal)

    return pq[0]

def generate_codes(node, current_code="", codes=None):
    """
    허프만 코드를 생성

    Args:
        node (HuffmanNode): 트리의 현재 노드
        current_code (str): 현재까지의 코드
        codes (dict): 문자별 코드를 저장할 딕셔너리

    Returns:
        dict: 문자별 허프만 코드
    """
    if codes is None:
        codes = {}

    if node is None:
        return codes

    if node.char is not None:  # 리프 노드
        codes[node.char] = current_code
        return codes

    # 왼쪽과 오른쪽 재귀 호출
    generate_codes(node.left, current_code + "0", codes)
    generate_codes(node.right, current_code + "1", codes)

    return codes

# 테스트
text = "hello world"
root = build_huffman_tree(text)
codes = generate_codes(root)

print("허프만 코드:")
for char, code in codes.items():
    print(f"'{char}': {code}")

3. 최소 신장 트리 - 크루스칼 알고리즘

문제: 그래프의 모든 정점을 연결하는 최소 비용 트리를 찾으세요.

def find(parent, i):
    """Union-Find의 Find 연산"""
    if parent[i] != i:
        parent[i] = find(parent, parent[i])  # 경로 압축
    return parent[i]

def union(parent, rank, x, y):
    """Union-Find의 Union 연산"""
    xroot = find(parent, x)
    yroot = find(parent, y)

    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

def kruskal_mst(edges, num_vertices):
    """
    크루스칼 알고리즘으로 MST 구하기

    Args:
        edges (list): [(가중치, 정점1, 정점2), ...] 형태의 간선 리스트
        num_vertices (int): 정점 개수

    Returns:
        list: MST를 구성하는 간선들
    """
    # 간선들을 가중치 기준으로 정렬
    edges.sort()

    parent = list(range(num_vertices))
    rank = [0] * num_vertices
    mst = []

    for weight, u, v in edges:
        # 사이클이 생성되지 않는 경우에만 간선 추가
        if find(parent, u) != find(parent, v):
            union(parent, rank, u, v)
            mst.append((u, v, weight))

    return mst

# 테스트
edges = [
    (7, 0, 1), (5, 0, 3), (8, 1, 2), (9, 1, 3),
    (7, 1, 4), (5, 2, 4), (15, 3, 4), (6, 4, 5),
    (8, 2, 5), (9, 3, 5), (11, 4, 5)
]

mst = kruskal_mst(edges, 6)
total_weight = sum(weight for _, _, weight in mst)

print("최소 신장 트리:")
for u, v, weight in mst:
    print(f"간선 ({u}, {v}): 가중치 {weight}")
print(f"총 가중치: {total_weight}")

4. 그리디 알고리즘의 한계와 해결책

그리디가 실패하는 경우

예시 1: 동전 거스름돈 (특정 동전 조합)

동전: [1, 3, 4]원
거스름돈: 6원

그리디 선택:
4원 → 1개 (남은 금액: 2원)
1원 → 2개 (남은 금액: 0원)
총 동전: 3개

최적해:
3원 → 2개
총 동전: 2개

예시 2: 배낭 문제 (일부 선택 가능)

물건: [(무게, 가치)] = [(2, 3), (3, 4), (4, 5), (5, 6)]
용량: 5

그리디 (가치 기준):
물건 4 (가치 6, 무게 5) → 선택
총 가치: 6

최적해:
물건 1 (가치 3, 무게 2) + 물건 2 (가치 4, 무게 3) = 가치 7

그리디 알고리즘 검증 방법

1. 최적성 증명 (Optimal Substructure)

• 전체 최적해가 부분 최적해로 구성되는지 증명

2. 그리디 선택 증명 (Greedy Choice Property)

• 첫 번째 선택이 항상 최적해에 포함되는지 증명

3. 귀납법 적용

• 작은 문제에서 성립하면 큰 문제에서도 성립함을 증명

5. 그리디 알고리즘 설계 패턴

1. 문제 분석

• 그리디 선택 가능성 확인
• 최적 부분 구조 확인
• 반례 존재 여부 확인

2. 그리디 전략 선택

• 가장 큰 것부터: 허프만 코딩, 크루스칼
• 가장 작은 것부터: 다익스트라, 허프만
• 가장 이른 종료 시간: 활동 선택

3. 구현 및 검증

• 의사코드 작성
• 반례 테스트
• 정당성 증명

6. 고급 그리디 기법

1. 우선순위 큐 활용

import heapq

def dijkstra_shortest_path(graph, start):
    """
    다익스트라 알고리즘 (그리디 + 우선순위 큐)

    Args:
        graph (dict): 그래프 (인접 리스트)
        start (int): 시작 정점

    Returns:
        dict: 각 정점까지의 최단 거리
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    pq = [(0, start)]  # (거리, 정점)

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

2. 그리디 + DP 하이브리드

def fractional_knapsack(items, capacity):
    """
    분할 가능 배낭 문제 (그리디)

    Args:
        items (list): [(무게, 가치), ...]
        capacity (int): 배낭 용량

    Returns:
        float: 최대 가치
    """
    # 단위 무게당 가치를 기준으로 정렬
    items.sort(key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0
    remaining_capacity = capacity

    for weight, value in items:
        if remaining_capacity >= weight:
            # 물건 전체 선택
            total_value += value
            remaining_capacity -= weight
        else:
            # 물건 일부 선택
            fraction = remaining_capacity / weight
            total_value += value * fraction
            break

    return total_value

7. 그리디 알고리즘 문제 해결 전략

1. 그리디 가능성 판단

• 매트로이드: 그리디가 최적해를 보장하는 구조
• 매트로이드 외: 반례 존재 가능성 높음

2. 증명 기법

• 교환论证: 그리디 선택이 다른 선택보다 우월함 증명
• 귀납법: 작은 경우에서 큰 경우로 확장

3. 구현 팁

• 정렬 활용: 대부분의 그리디는 정렬로 시작
• 우선순위 큐: 실시간 선택이 필요할 때
• 반례 테스트: 구현 후 다양한 케이스로 검증

8. 연습 문제

1. 그리디 알고리즘이 실패하는 동전 거스름돈 문제를 찾아보세요.

2. 허프만 코딩에서 빈도가 같은 문자들의 우선순위는 어떻게 결정되나요?

3. 크루스칼 알고리즘에서 Union-Find 자료구조가 왜 필요한가요?

4. 그리디 알고리즘을 사용할 수 없는 문제의 예시를 들어보세요.

마무리

그리디 알고리즘은 단순하지만 강력한 문제 해결 도구입니다. 모든 문제에 적용할 수는 없지만, 적용 가능한 문제에서는 매우 효율적입니다.

핵심 요약:

• 그리디 = 순간 최선의 선택 반복
• 전제 조건: 최적 부분 구조 + 그리디 선택 속성
• 대표 문제: 활동 선택, 허프만 코딩, 크루스칼
• 한계: 미래 고려 불가, 반례 존재 가능
• 검증: 최적성 증명 + 반례 테스트

다음 글에서는 분할 정복 알고리즘에 대해 알아보겠습니다. 큰 문제를 작은 문제로 나누어 해결하는 체계적인 방법을 배워보겠습니다!

추가 팁: 그리디 알고리즘을 적용하기 전에 먼저 반례를 찾아보세요. 그리디가 항상 옳은 것은 아닙니다! 🎯💡