그리디 기초

그리디란?

그리디(greedy, 탐욕법) 는 매 순간 가장 좋아 보이는 선택을 하면서 전체
최적해에 도달하는 방법입니다. 멀리 내다보지 않고 눈앞의 최선만 고르는데도
전체 답이 최적이 되는, 신기하지만 강력한 전략입니다.

핵심은 "언제 그리디가 옳은가" 를 아는 것입니다. 아무 문제에나 그리디를 쓰면
틀립니다.

1. 그리디가 통하는 두 조건

그리디가 최적해를 보장하려면 보통 다음 두 성질이 필요합니다.

• 탐욕적 선택 속성(greedy choice property): 매 단계의 지역적 최선 선택이
  전체 최적해의 일부가 된다.
• 최적 부분 구조(optimal substructure): 한 번 선택한 뒤 남은 문제도 같은
  방식으로 풀린다.

이 두 가지를 증명할 수 있어야 그리디를 안심하고 씁니다.

2. 고전 예: 동전 거스름돈

500, 100, 50, 10원 동전으로 거스름돈을 줄 때, 큰 동전부터 최대한 쓰면 동전
개수가 최소가 됩니다.

1260원 = 500×2 + 100×2 + 50×1 + 10×1  → 6개 (최적)

이것이 통하는 이유는 큰 단위가 작은 단위의 배수라서 큰 걸 안 쓰면 손해이기
때문입니다. 하지만 동전이 {1, 3, 4}처럼 배수 관계가 깨지면 그리디가 틀립니다
— 6원을 4+1+1(3개)로 만들지만 최적은 3+3(2개)입니다. 그리디의 함정을 보여 주는
대표 예입니다.

3. 정렬이 거의 항상 동반된다

그리디 문제는 대부분 "어떤 기준으로 정렬한 뒤 순서대로 선택" 하는 형태입니다.
그래서 "무엇을 기준으로 정렬해야 그리디가 옳은가"를 찾는 것이 풀이의 핵심입니다.

• 회의실 배정 → 끝나는 시간 기준 정렬.
• 최소 동전 → 큰 단위부터.
• 마감 있는 작업 → 마감/이득 기준 정렬.

4. 대표 문제: 활동 선택(회의실 배정)

겹치지 않게 최대한 많은 회의를 잡는 문제. 끝나는 시간이 빠른 회의부터 고르면
최적입니다.

직관: 가장 일찍 끝나는 회의를 고르면 뒤에 남는 시간이 가장 많아져, 더 많은
회의를 넣을 여지가 생깁니다. 이 "교환 논증(exchange argument)"이 그리디
정당성 증명의 전형입니다.

5. 그리디 vs DP

그리디와 DP는 둘 다 최적 부분 구조를 쓰지만 다릅니다.

그리디가 옳음을 증명하기 어렵다면, 안전하게 DP로 푸는 것이 낫습니다.

정리

그리디는 매 순간의 최선으로 전체 최적에 도달합니다. 핵심은 올바른 정렬 기준을
찾고 그것이 옳음을 증명하는 것. 배수 관계가 깨진 동전 예처럼, 검증 없는 그리디는
위험합니다. 다음 강의에서 대표 문제들을 코드로 풉니다.

그리디를 코드로, 그리고 의심하기

대표 그리디 문제들을 구현하면서, 그리디가 옳은지 검증하는 습관을 기릅니다.

1. 회의실 배정 (활동 선택)

겹치지 않는 최대 회의 수. 끝나는 시간 기준 정렬 후, 직전 회의가 끝난 뒤
시작하는 회의를 차례로 고릅니다.

sort(meet.begin(), meet.end(), [](auto& a, auto& b){
    if (a.second != b.second) return a.second < b.second;  // 끝나는 시간
    return a.first < b.first;                              // 동률은 시작 빠른 것
});
int cnt = 0, end = -1;
for (auto& [s, e] : meet)
    if (s >= end) { cnt++; end = e; }   // 직전 끝난 뒤 시작 가능하면 선택

meet.sort(key=lambda x: (x[1], x[0]))   # (끝나는 시간, 시작 시간)
cnt, end = 0, -1
for s, e in meet:
    if s >= end:
        cnt += 1
        end = e

2. 최소 동전 개수 (배수 관계일 때만!)

sort(coins.rbegin(), coins.rend());     // 큰 단위부터
int cnt = 0;
for (int c : coins) {
    cnt += money / c;                   // 이 단위를 최대한 사용
    money %= c;
}

다시 강조: 이 그리디는 동전이 배수 관계일 때만 옳습니다. 아니면 DP를 쓰세요.

3. 마감 있는 작업 스케줄링

각 작업에 마감과 이득이 있을 때 이득 합을 최대화. 이득 큰 순으로 정렬하고,
가능한 가장 늦은 빈 시간에 배치합니다(우선순위 큐를 쓰는 변형도 있음).

sort(jobs.begin(), jobs.end(), [](auto&a, auto&b){
    return a.profit > b.profit;          // 이득 큰 것부터
});
vector<bool> slot(maxDeadline + 1, false);
long long total = 0;
for (auto& j : jobs)
    for (int t = j.deadline; t >= 1; t--)   // 가능한 늦은 시간부터
        if (!slot[t]) { slot[t] = true; total += j.profit; break; }

4. 그리디 정당성: 교환 논증

그리디가 옳다는 증명의 표준 틀이 교환 논증입니다.

최적해가 그리디의 선택과 다르다고 가정하자. 최적해의 한 선택을 그리디의
선택으로 바꿔도(swap) 답이 나빠지지 않음을 보이면, 그리디 선택을 포함한
최적해가 존재한다.

회의실 배정에서 "가장 일찍 끝나는 회의로 바꿔도 손해가 없다"가 바로 이것입니다.
이 논증이 머릿속에서 막히면, 그리디가 틀린 신호일 수 있습니다.

5. 그리디 검증: 완전 탐색과 대조

확신이 안 서면, 작은 입력에서 완전 탐색(brute)과 그리디의 답을 비교하는
스트레스 테스트를 돌리세요. 반례가 나오면 그리디가 틀린 것입니다.

# 무작위 입력 생성 → greedy(x)와 brute(x)가 다르면 반례 출력

이 습관 하나가 잘못된 그리디로 인한 오답을 막아 줍니다.

6. 흔한 실수

• 잘못된 정렬 기준 — "시작 시간"으로 정렬하면 회의실 배정이 틀립니다.
  반드시 "끝나는 시간".
• 증명 없는 그리디 — 직관만으로 제출하면 함정 입력에 당합니다.
• 배수 아닌 동전에 그리디 — DP로 가야 합니다.
• 동률 처리 — 같은 키일 때의 2순위를 정하지 않아 답이 흔들리는 경우.

7. 패턴 알아보기

• "최대한 많이/적게 ~", "겹치지 않게 ~", "마감/순서 최적화" → 그리디 후보.
• "정렬하면 답이 보일 것 같다" → 정렬 기준을 찾고 교환 논증으로 검증.
• 증명이 막히거나 반례가 나오면 → DP로 전환.

실전에서 그리디 문제 알아보기

그리디의 진짜 어려움은 구현이 아니라 "이 그리디가 맞다고 어떻게 확신하나"
입니다. 신호를 읽고, 반례를 사냥하고, 확신을 얻는 절차를 다룹니다.

1. 출제 신호

• "최소 개수", "최대한 많이" + 한 번의 선택이 이후 선택을 단순하게만
  제약하는 구조 — 회의실 배정, 동전 거스름돈.
• 정렬하고 나면 풀이가 한 번 훑기로 끝날 것 같은 느낌 — 그리디의 절반은
  "어떤 순서로 처리할 것인가"입니다.
• 교환해도 손해가 없음을 보일 수 있다 — 두 선택의 순서를 바꿨을 때 답이
  나빠지지 않으면(교환 논증) 그리디가 성립합니다.
• 제한이 커서(\(N \le 10^5\) 이상) DP의 상태 공간이 안 나올 때 — 출제자가
  \(O(N \log N)\) 그리디를 기대한다는 간접 신호입니다.

2. 풀이 결정 절차

1. 그리디 기준 후보를 2~3개 적습니다 — "일찍 끝나는 순", "짧은 순",
   "비싼 순" 등.
2. 각 기준에 대해 5분간 작은 반례를 손으로 만들어 봅니다. 반례가 나온
   기준은 버립니다.
3. 살아남은 기준에 교환 논증을 적용합니다 — 최적해에서 내 기준과 다른
   첫 선택을 내 것으로 바꿔도 손해가 없는가?
4. 그래도 불안하면 작은 입력에서 완전 탐색과 답 대조(스트레스 테스트)로
   확신을 얻고 제출합니다.

3. 자주 하는 실수

• 회의실 배정을 시작 시간 순으로 정렬. 길게 끄는 회의 하나가 여러 개를
  막습니다. 끝나는 시간 기준이 정답이고, 동률이면 시작 시간으로 묶습니다.

sort(v.begin(), v.end(), [](auto& a, auto& b) {
    if (a.end != b.end) return a.end < b.end;   // 끝나는 시간 우선
    return a.start < b.start;                   // (0길이 회의 처리용)
});
int cnt = 0, cur = -1e9;
for (auto& m : v)
    if (m.start >= cur) { cnt++; cur = m.end; }

• 동전 그리디 과신. 큰 동전부터 빼는 그리디는 동전이 서로 배수 관계
  (1, 5, 10, 50, …)일 때만 보장됩니다. {100, 400, 500}에서 800원은 그리디가
  500+100×3(4개), 정답은 400×2(2개)입니다. 임의 단위면 DP로 가야 합니다.
• 동률 처리(tie-break) 빠뜨림. 1차 키만 정렬하면 같은 값끼리의 순서가
  답을 바꾸는 문제가 많습니다. 동률 규칙까지 비교자에 명시하세요.
• 지역 최적의 단위를 잘못 잡음. "지금 당장 이득"의 정의가 여러 개일 때
  아무거나 골라 짜기 시작하면 반례를 맞습니다. 반드시 2번 절차(반례 사냥)를
  거치세요.
• 반례 없이 제출 → 틀림 → 같은 기준 재제출. 틀렸다면 기준 자체를
  바꿔야지, 구현만 다듬으면 같은 반례에 또 걸립니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 동전·회의실
같은 고전부터, 기준이 비자명해 교환 논증이 꼭 필요한 문제로 이어집니다.

각 문제에서 채택한 기준과 "왜 교환해도 손해가 없는가" 한 문장을 풀이
노트에 남기는 습관을 들이세요. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.