왜 그리디가 구간 스케줄링에 작동하는가? 증명
Source: Dev.to
원래는 LeetCopilot Blog 에서 게시되었습니다.
TL;DR
- Topic: 최소 종료 시간 탐욕 알고리즘을 사용하여 겹치지 않는 구간을 최대 개수 선택하기.
- Why it matters: 면접에서는 단순히 정렬된 루프를 작성하는 것이 아니라 탐욕 선택을 정당화할 수 있는지를 테스트한다.
- Core steps:
- 구간을 종료 시간 기준으로 정렬한다.
- 한 번 스캔하면서 시작 시간이
lastEnd이상인 구간을 유지한다. - 선택할 때마다
lastEnd를 업데이트한다.
- Common confusion: 시작 시간으로 정렬하거나
lastEnd경계를 업데이트하는 것을 잊는 경우. - You’ll learn: 그림으로 보기 쉬운 추적, 짧은 증명 아이디어, 최소 코드 스니펫, 그리고 연습 문제.
초보자 친화적인 설명: 왜 가장 이른 종료가 승리하는가
직관 – 더 빨리 끝나면 더 많은 구간을 위한 공간이 확보됩니다. 가장 이른 종료 시간을 선택하면 남은 공간을 최대화할 수 있습니다.
교환 논증 – 다른 호환 가능한 구간보다 나중에 끝나는 구간을 선택한다면, 답을 감소시키지 않으면서 더 이른 종료 구간으로 교체할 수 있습니다. (기사 *Greedy Algorithm Counterexamples for Coding Interviews*에 있는 반례 습관을 참고하세요.)
경계 추적 – lastEnd를 마지막으로 수락된 구간의 종료 시간으로 유지하면서 불변식을 유지합니다.
단계별 학습 가이드
-
끝 시간 기준 정렬
시작 시간 기준 정렬은 흔히 빠지는 함정입니다. 끝 시간 기준으로 정렬하면 교환 논리가 보장됩니다. -
한 번에 순회
각 구간에 대해start >= lastEnd이면 선택하고lastEnd를 업데이트합니다. 이는 *Greedy or DP for Coin Change Decisions*에서 논의된 단조‑패스 원칙과 동일합니다. -
불변식 서술
“lastEnd는 지금까지 선택한 구간들 중 가장 이른 종료 경계입니다. 나는 이 경계 이후에 시작하는 구간만 허용합니다.” 라고 말합니다. -
반례 검증
더 일찍 끝나는 호환 가능한 구간을 놓치지 않았는지 확인합니다. 만약 발견된다면, 교환을 통해 용량이 유지되거나 증가하므로 올바름이 유지됩니다. -
다양한 구간으로 연습
겹치는 구간, 중첩된 구간, 종료 시간이 같은 구간 등을 사용해 언제 업데이트가 일어나는지 확실히 익히세요.
시각화 가능한 예시: 추적 테이블
Intervals (start, end) sorted by end:
[1,2], [2,3], [1,3], [3,4], [2,5]
Pick [1,2] → lastEnd = 2
Pick [2,3] (start >= lastEnd) → lastEnd = 3
Skip [1,3] (starts before lastEnd)
Pick [3,4] → lastEnd = 4
Skip [2,5] (starts before lastEnd)가로 막대를 그리면 호환성을 빠르게 확인할 수 있습니다.
코드 예시: Earliest‑Finish Greedy
def interval_scheduling(intervals):
# Sort by end time
intervals.sort(key=lambda x: x[1])
chosen = []
last_end = float('-inf')
for start, end in intervals:
if start >= last_end: # compatible?
chosen.append((start, end))
last_end = end
return chosen이 코드는 단일 경계를 추적하고, 그 경계 이후에 시작하는 구간을 받아들여 불변식을 구현합니다.
실전 준비 전략
- Swap‑proof rehearsal: 종이 위에서 교환 논증을 1분 동안 설명하는 연습을 하세요.
- Edge‑case drills: 끝 시간이 동일하고 길이가 0인 구간을 포함하세요.
- Contrast exercises: 시작 시간으로 정렬해 보면서 왜 실패하는지 확인하고, 그 다음 끝 시간으로 정렬해 다시 시도하세요.
- Guided review: LeetCopilot과 같은 도구는 겹침을 시각화하고, 건너뛴 구간을 더 일찍 교환할 수 있었는지 빠르게 보여줍니다.
피해야 할 일반적인 실수
| 실수 | 왜 문제가 되는가 |
|---|---|
| 시작 시간 기준 정렬 | 일찍 시작하지만 늦게 끝나는 구간을 놓쳐 최적의 집합을 놓치게 되고, 이후 선택을 방해합니다. |
| 겹침을 실수로 허용 | start >= lastEnd 검사를 빼먹으면 호환되지 않는 구간을 선택하게 되어 최댓값을 유지하지 못합니다. |
| 경계가 같은 경우 오해 | 구간이 서로 맞닿아 있는 경우(end == start)를 허용할지 여부를 명확히 해야 합니다; 대부분의 면접 변형에서는 허용합니다. |
| 코드 과다 설명, 증명 부족 설명 | 면접관은 루프 자체보다 탐욕 알고리즘이 왜 안전한지에 더 관심을 가집니다. |
FAQ
탐욕 알고리즘이 허용되는지 어떻게 알 수 있나요?
미래의 용량에 영향을 주지 않는 지역 최적 선택을 정의하고, 교환 논증으로 이를 정당화할 수 있다면 탐욕 알고리즘이 유망합니다.
이전에 무엇을 공부해야 하나요?
기본적인 정렬 안정성을 복습하고, How to Know When Dynamic Programming Is Needed 에서 제시된 결정 가이드를 다시 살펴보면서 탐욕과 대비해 보세요.
가장 이른 종료 규칙이 유일한가요?
구간의 개수를 최대화할 때는 예합니다; 다른 순서는 용량을 차단할 위험이 있습니다.
가중치가 있는 구간을 어떻게 처리하나요?
가중치가 있는 경우에는 DP가 필요합니다; 구간마다 값이 다르면 단순 탐욕 알고리즘은 실패합니다.
결론
Earliest‑finish greedy는 매번 가능한 가장 작은 경계를 고정하기 때문에 작동하며, 이는 향후 선택을 위한 최대의 여지를 남깁니다. 교환 논증을 연습하고, 예시를 추적하며, lastEnd를 불변 조건으로 유지함으로써 인터뷰에서 구간 스케줄링을 자신 있게 설명하고 구현할 수 있습니다.
LeetCode 패턴을 마스터하고 인터뷰 준비를 도와줄 AI 어시스턴트를 찾고 있다면, LeetCopilot을 확인해 보세요!
코딩 인터뷰를 위해, LeetCopilot을 확인해 보세요.