알고리즘
탐욕 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하고 되돌리지 않는 설계 방법으로, 구간 스케줄링·허프만 부호화·분할 가능 배낭 문제를 빠르게 풉니다.
탐욕 알고리즘(greedy algorithm)은 문제를 여러 단계의 선택으로 나누고, 각 단계에서 정해진 기준으로 지금 가장 좋아 보이는 후보를 고른 뒤 그 결정을 다시 돌아보지 않는 알고리즘 설계 방법입니다. 후보를 정렬하거나 우선순위 큐에 넣고 하나씩 꺼내며 받아들일지 정하는 구조가 대부분이라 코드가 짧고, 시간 복잡도는 보통 정렬이나 힙 연산이 정하는 O(n log n)입니다.
탐욕 알고리즘은 맞는 문제에서는 가장 빠르고 단순한 해법이지만, 언제나 맞지는 않습니다. 최적해를 보장하려면 탐욕 선택 속성과 최적 부분 구조가 성립해야 하고, 보통 교환 논법으로 이를 증명합니다. 동전 1, 3, 4원으로 6원을 만드는 문제처럼 반례가 하나라도 있으면 동적 계획법을 써야 합니다. 허프만 부호화, 다익스트라 최단 경로, 최소 신장 트리처럼 실무에서 쓰이는 핵심 알고리즘에도 탐욕 원리가 들어 있습니다.
공부할 때는 구간 스케줄링(활동 선택)부터 시작해 '가장 일찍 끝나는 것을 고른다'는 기준이 왜 옳은지 교환 논법으로 설명해 보는 것이 좋습니다. 이어서 허프만 부호화, 분할 가능 배낭, 힙을 이용한 회의실 배정을 직접 구현하고, 작은 입력에서 완전 탐색과 결과를 비교하는 습관을 들이면 코딩 테스트에서 틀린 탐욕 기준을 빨리 걸러 낼 수 있습니다.
첫 탐욕 선택을 포함하는 최적해가 항상 존재해야 하며, 이것이 탐욕 알고리즘이 옳기 위한 핵심 조건입니다.
임의의 최적해를 탐욕 해 쪽으로 한 원소씩 바꿔도 손해가 없음을 보여 탐욕 기준의 정당성을 증명합니다.
후보를 끝 시간, 무게당 가치, 빈도 같은 기준으로 줄 세우거나 힙에서 꺼내므로 대개 O(n log n)에 동작합니다.
임의의 동전 체계 거스름돈이나 0/1 배낭처럼 탐욕이 틀리는 문제에서는 동적 계획법으로 바꿔야 합니다.
겹치지 않는 회의를 가장 많이 고르는 구간 스케줄링입니다. 회의를 끝나는 시간순으로 정렬한 뒤, 직전에 고른 회의가 끝난 뒤에 시작하는 회의만 받아들입니다. 정렬이 O(n log n), 훑기가 O(n)이며, 예제에서는 11개 회의 중 4개를 고릅니다.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.py탐욕 알고리즘 에 관해 묻고, 경험을 나누고, 의견을 주고받는 곳입니다.
아직 토론이 없습니다. 첫 이야기를 시작해 보세요.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.