탐욕 알고리즘은 교과서 문제에만 있지 않습니다. 압축 형식, 그래프 알고리즘, 운영체제와 클러스터의 스케줄러 곳곳에 들어 있습니다. 또 최적해를 보장하지 못하는 문제에서도 "충분히 좋은 답을 빠르게" 내는 근사 알고리즘으로 널리 쓰입니다.
실제 시스템 속의 탐욕
DEFLATE는 LZ77로 반복을 줄인 뒤, 남은 기호와 길이 값을 허프만 부호로 적습니다. 규격(RFC 1951)은 부호 길이만 저장하고 실제 비트열은 정준 허프만 규칙으로 복원하게 되어 있어서, 앞 장에서 만든 huffman_code_lengths 같은 함수가 그대로 쓰입니다. 다만 실제 구현은 최대 부호 길이(15비트) 제한을 맞추기 위해 길이를 조정하는 단계가 더 있습니다.
근사 알고리즘으로서의 탐욕
NP-난해 문제에서는 최적해를 빠르게 구할 방법이 알려져 있지 않으므로, 증명된 근사 비율을 가진 탐욕이 실무 기본값이 되곤 합니다.
작업을 기계 여러 대에 나눌 때 긴 작업부터 가장 덜 바쁜 기계에 주는 LPT(Longest Processing Time) 규칙은 가장 늦게 끝나는 시각이 최적의 4/3배를 넘지 않음이 알려져 있습니다.
import heapq
def lpt_assign(jobs, machines):
heap = [(0, m) for m in range(machines)] # (부하, 기계 번호)
plan = [[] for _ in range(machines)]
for job in sorted(jobs, reverse=True):
load, m = heapq.heappop(heap)
plan[m].append(job)
heapq.heappush(heap, (load + job, m))
return plan, max(sum(p) for p in plan)
print(lpt_assign([7, 5, 4, 4, 3, 3, 2], 3)) # ([[7, 3], [5, 3, 2], [4, 4]], 10)
집합 덮개 문제에서는 아직 덮이지 않은 원소를 가장 많이 덮는 집합을 반복해서 고릅니다. 이 탐욕은 최적의 약 ln n배 이내를 보장하며, P ≠ NP라면 다항 시간 알고리즘으로는 이보다 크게 나을 수 없다는 결과도 알려져 있습니다. 테스트 케이스 선택, 기지국이나 창고 위치 선정에 자주 쓰입니다.
def greedy_set_cover(universe, subsets):
uncovered, picked = set(universe), []
while uncovered:
best = max(subsets, key=lambda name: len(subsets[name] & uncovered))
if not subsets[best] & uncovered:
return None # 덮을 수 없는 원소가 있다
picked.append(best)
uncovered -= subsets[best]
return picked
regions = {"A": {1, 2, 3, 4}, "B": {4, 5, 6}, "C": {6, 7}, "D": {1, 5, 7}}
print(greedy_set_cover(range(1, 8), regions)) # ['A', 'B', 'C']
자주 하는 실수
- 증명 없이 기준을 고르기: 예제 몇 개가 맞는다고 옳은 것이 아닙니다. 작은 무작위 입력으로 완전 탐색과 비교하는 시험을 꼭 둡니다.
- 구간 경계: 반열린 구간인지 닫힌 구간인지에 따라
<와 <=가 바뀝니다. 문제 문장과 테스트에 경계 사례를 넣습니다. - 힙에 비교할 수 없는 값 넣기: 무게가 같으면 Python은 튜플의 다음 값을 비교하므로, 딕셔너리나 사용자 객체가 오면
TypeError가 납니다. 사이에 증가하는 번호를 넣습니다. - 부동소수점 비율: 가치/무게 비율을 실수로 정렬하면 동점 판정이 흔들릴 수 있습니다. 곱셈 비교나
Fraction을 씁니다. - 문제 변형 놓치기: 가중치가 붙거나 물건을 쪼갤 수 없게 되면 같은 탐욕이 틀립니다.
아래는 무작위 입력으로 탐욕 해를 완전 탐색과 비교하는 시험의 뼈대입니다.
import itertools
import random
def brute_force(intervals):
for k in range(len(intervals), 0, -1):
for combo in itertools.combinations(sorted(intervals), k):
if all(a[1] <= b[0] for a, b in zip(combo, combo[1:])):
return k
return 0
def greedy_count(intervals):
count, last_end = 0, float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]):
if start >= last_end:
count, last_end = count + 1, end
return count
for _ in range(500):
data = [(s, s + random.randint(1, 5)) for s in random.choices(range(10), k=6)]
assert greedy_count(data) == brute_force(data), data
print("모두 통과")
더 읽을거리
정리
- 허프만 부호는 DEFLATE와 JPEG에, 다익스트라 · 프림 · 크루스칼은 그래프 처리에 쓰이는 대표 탐욕 알고리즘입니다.
- LPT 배치와 집합 덮개처럼 최적을 보장하지 못하는 문제에서도 탐욕은 근사 비율이 증명된 실용적인 기본값입니다.
- 실무에서는 경계 조건, 힙의 동점 처리, 실수 비교, 문제 변형을 특히 조심합니다.
- 탐욕 코드를 배포하기 전에 작은 입력에서 완전 탐색과 비교하는 시험을 남겨 두면 안전합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.