핵심 정리
| 질문 | 확인할 점 |
|---|---|
| 현재 선택이 안전한가 | 나중에 바꿀 필요가 없는가 |
| 정렬 기준이 있는가 | 작은 것부터, 끝나는 시간부터 등 |
| 반례가 없는가 | 작은 케이스로 깨지는지 |
| DP와 다른가 | 이전 선택 조합을 기억할 필요가 없는가 |
text
정렬한다
현재 기준에서 가장 좋아 보이는 선택을 한다
선택 후 조건을 갱신한다
끝까지 반복한다구조
그리디는 각 단계에서 가장 좋아 보이는 선택을 하고, 그 선택을 되돌리지 않습니다. 핵심은 “지금의 최선이 전체 최선으로 이어진다”는 근거입니다.
예를 들어 회의실 배정 문제에서는 끝나는 시간이 빠른 회의를 먼저 고르는 전략이 성립합니다. 일찍 끝날수록 뒤에 남는 시간이 많아지고, 이 선택은 다른 최적해와 교환해도 손해가 없다는 식으로 설명할 수 있습니다.
csharp
meetings.Sort((a, b) =>
{
int byEnd = a.End.CompareTo(b.End);
if (byEnd != 0) return byEnd;
return a.Start.CompareTo(b.Start);
});
int count = 0;
int currentEnd = int.MinValue;
foreach (var meeting in meetings)
{
if (meeting.Start < currentEnd) continue;
count++;
currentEnd = meeting.End;
}선택 기준
| 문제 신호 | 판단 |
|---|---|
| 정렬 후 앞에서부터 선택 | 그리디 후보 |
| 선택을 되돌릴 필요 없음 | 그리디 가능성 |
| 교환 논리로 증명 가능 | 그리디 강함 |
| 현재 선택이 미래 선택을 복잡하게 제한 | DP 검토 |
| 모든 조합 비교가 필요 | 백트래킹 또는 DP 검토 |
그리디 문제는 구현보다 정렬 기준을 찾는 것이 핵심입니다. 기준이 하나가 아니라면 1차, 2차 정렬 조건까지 명확히 잡아야 합니다.
주의할 점
“가장 큰 것부터”, “가장 작은 것부터”가 항상 정답은 아닙니다. 작은 반례를 만들었을 때 깨지면 그리디가 아니라 DP나 탐색 문제일 수 있습니다.
그리디 풀이는 증명 없이 감으로 제출하면 위험합니다. 최소한 선택을 바꿔도 손해가 없다는 교환 논리나, 현재 선택이 미래 가능성을 가장 덜 해친다는 근거를 확인하세요.
참고 링크
1 sources