그리디 알고리즘 쉽게 이해하기: 동작 원리, 코드, 예제

그리디 알고리즘이 해결하는 문제

그리디 알고리즘은 최적화 문제를 겨냥합니다. 가장 많은 활동 고르기, 가장 적은 동전 쓰기, 가장 싼 네트워크 만들기, 파일을 가장 적은 비트로 압축하기 같은 문제입니다. 모든 조합을 탐색하는 대신 선택지를 정렬하거나 우선순위를 매기고 매 단계에서 가장 좋은 것을 확정합니다. 보통 시간 복잡도는 정렬 비용인 O(n log n) 정도입니다.

어려운 부분은 코드가 아니라 증명입니다. 자연스러워 보이는 그리디 규칙 중 많은 것이 틀리므로, 규칙이 올바르다는 것을 증명하거나 완전 탐색 풀이와 비교해 테스트해야 합니다.

핵심 아이디어

1. 선택지의 순위를 매기는 규칙을 찾습니다. 예를 들면 "끝나는 시각이 이른 것 먼저"나 "가벼운 간선 먼저"입니다.
2. 그 규칙으로 선택지를 정렬하거나 우선순위 큐에 보관합니다.
3. 선택지를 차례로 살펴보며 제약을 어기지 않는 것은 모두 선택합니다.
4. 한 번 한 선택은 절대 되돌리지 않습니다.

그리디 알고리즘은 두 가지 속성이 성립할 때 올바릅니다. 탐욕 선택 속성: 최초의 그리디 선택을 포함하는 최적해가 존재합니다. 최적 부분 구조: 그 선택을 한 뒤 남은 문제가 같은 문제의 더 작은 인스턴스입니다. 일반적인 증명은 교환 논증입니다. 임의의 최적해를 잡아 그 선택 중 하나를 그리디 선택으로 바꿔도 결과가 나빠지지 않음을 보입니다.

예제: 구간 스케줄링

회의실이 하나 있고 요청이 (시작, 끝)으로 다음과 같습니다. A (1, 4), B (3, 5), C (0, 6), D (5, 7), E (3, 9), F (5, 9), G (6, 10), H (8, 11). 겹치지 않는 회의를 가능한 한 많이 예약하려고 합니다. 올바른 그리디 규칙은 마지막으로 예약한 회의가 끝난 뒤에 시작하는 회의 중 가장 먼저 끝나는 회의를 항상 고르는 것입니다.

결과: A, D, H, 회의 세 개이며 이것이 최대입니다. 동작하는 이유: 가장 먼저 끝나는 회의가 나머지 모든 것에 가장 많은 시간을 남기므로, 어떤 최적 일정의 첫 회의를 이 회의로 바꿔도 충돌이 생기지 않습니다.

파이썬 구현

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

두 번째 대표 예는 분할 가능 배낭 문제입니다. 물건의 일부를 가져갈 수 있다면 무게 단위당 가치가 높은 순으로 가져가는 것이 최적입니다.

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

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

그리디가 실패하는 경우: 반례

시간 복잡도와 공간 복잡도

공간은 보통 정렬한 사본이나 힙을 위한 O(n)입니다. 입력이 이미 정렬되어 있으면 많은 그리디 알고리즘이 O(n)에 동작합니다.

그리디를 쓰는 경우와 실제 활용

• 탐욕 선택 속성을 증명할 수 있거나 빠른 근삿값으로 충분할 때 그리디를 사용하세요. 그렇지 않다면 동적 계획법이나 백트래킹을 사용합니다.
• 압축: 허프만 코딩은 빈도가 가장 낮은 두 심볼을 반복해서 병합해 최적의 접두사 코드를 만들며, DEFLATE(ZIP, gzip, PNG) 같은 포맷 안에서 쓰입니다.
• 네트워크: 최소 신장 트리(크루스칼, 프림)와 최단 경로 라우팅(다익스트라).
• 스케줄링: 마감 시한이 빠른 순, 그리고 회의실이나 기계 예약.
• 근사: 집합 커버 문제에서 "아직 덮이지 않은 원소를 가장 많이 덮는 집합 고르기"라는 그리디 규칙은 최적은 아니지만 최적해의 로그 배 이내임이 보장됩니다.
• 코딩 인터뷰 문제: 점프 게임, 주유소, 쿠키 나누어 주기, 겹치지 않는 구간, 풍선을 터뜨리는 최소 화살 수, 작업 스케줄러.