그리디

예약 신청 4개를 놓고, 두 가지 규칙의 결과가 어떻게 갈리는지 손으로 따라가 봅니다. 괄호는 (시작, 끝)입니다.

신청: (1, 4), (3, 5), (0, 6), (5, 7)

규칙 A — 일찍 시작하는 순: (0,6) → (1,4) → (3,5) → (5,7)

결과: 1개

규칙 B — 일찍 끝나는 순: (1,4) → (3,5) → (0,6) → (5,7)

결과: 2개

같은 "훑으면서 고르기"인데 순서를 정하는 기준 하나로 답이 달라집니다. 그리디 문제의 절반은 여기서 결정납니다.

그리디 풀이의 골격은 "기준을 정하고 → 그 순서로 정렬하고 → 한 번 훑으며 고른다"입니다.

1. 고르는 기준을 정합니다 — 후보(시작 / 끝 / 길이 / 비율)마다 작은 반례를 만들어 보고 결정합니다. 위 예시에서는 "끝나는 시각"이 기준이었습니다.

2. 그 기준으로 정렬합니다.

intervals.sort((a, b) => a[1] - b[1]); // 끝나는 시각 오름차순

3. 한 번만 훑으며 "지금 고를 수 있으면 고른다"를 반복합니다. 이때 지금까지의 선택 결과를 담아 둘 변수 하나가 필요합니다.

let count = 0;
let lastEnd = -Infinity; // 마지막으로 고른 예약이 끝난 시각

4. 겹치지 않을 때만 고르고, 상태를 갱신합니다.

for (const [s, e] of intervals) {
  if (s >= lastEnd) { count++; lastEnd = e; }
}

전체 코드 — "겹치지 않게 최대한 많은 예약 받기":

function solution(intervals: number[][]): number {
  // 2단계: 끝나는 시각 기준 정렬
  intervals.sort((a, b) => a[1] - b[1]);
  // 3단계: 상태 변수 준비
  let count = 0;
  let lastEnd = -Infinity;
  // 4단계: 한 번 훑으며 고를 수 있으면 고름
  for (const [s, e] of intervals) {
    if (s >= lastEnd) {
      count++;
      lastEnd = e;
    }
  }
  return count;
}

정렬이 O(N log N), 훑기가 O(N)이므로 전체는 O(N log N) 입니다. 모든 경우를 보는 DP·완전탐색보다 훨씬 빠릅니다.

• "최대한 많이 / 최소 횟수로 / 가장 적은 개수로" 를 묻는데, 각 선택이 서로 독립적이면 그리디 신호입니다.
• 입력을 어떤 순서로 정렬하면 답이 보일 것 같다는 느낌이 들면 그리디입니다 — 그 느낌의 정체가 "정렬 기준"입니다.
• 대표 상황: 겹치지 않는 회의·예약 최대 개수, 동전·단위로 개수 최소화, 두 배열을 짝지어 합/곱을 최대·최소로 만들기.
• 반대로 "쪼갤 수 없는 선택 + 가치 비율"(0-1 배낭)이거나 앞의 선택이 뒤의 선택 가능성을 복잡하게 바꾸면 DP 신호입니다.

• 정렬 기준을 감으로 정함 — 후보 기준(시작/끝/길이/비율)마다 반례를 만들어 보고 결정

intervals.sort((a, b) => a[0] - b[0]); // 시작 순 — "아주 작은 예시"에서 1개만 고름
intervals.sort((a, b) => a[1] - b[1]); // 끝 순 — 2개

• 그리디로 안 되는 문제(0-1 배낭 등)에 그리디 적용 — "쪼갤 수 없는 선택 + 가치 비율"은 DP 신호
• 동률 처리 미정의 — 끝나는 시각이 같을 때의 규칙까지 비교 함수에 명시

intervals.sort((a, b) => a[1] - b[1]);                       // 동률이면 순서 미정
intervals.sort((a, b) => a[1] - b[1] || a[0] - b[0]);        // 동률이면 늦게 시작한 것 우선

• "지금 가능한 것 중 최고"가 시각에 따라 변하는 문제 — 힙과 결합해야 함 (힙 토픽 참조)

그리디가 맞는지 확인하는 법 — 교환 논증

"내 그리디 선택 대신 다른 선택을 한 최적해가 있다고 하자. 그 선택을 내 것으로 바꿔치기해도 나빠지지 않는가?" — 나빠지지 않으면 그리디가 최적입니다. 구간 스케줄링이라면: 최적해의 첫 구간을 "가장 빨리 끝나는 구간"으로 바꿔도 뒤 일정에 더 많은 자리가 남으므로 손해가 없습니다.

거스름돈 500/400/100에서 800원을 만들 때 큰 단위 우선(500+100×3 = 4개)이 400×2(2개)에 지는 것처럼, 근거 없는 그리디는 반례에 무너집니다. 확신이 없으면 작은 입력으로 완전탐색과 비교해 보세요.

DP처럼 모든 경우를 보지 않으므로 빠르지만(대개 정렬 후 O(N log N)), "왜 그 선택이 손해가 아닌가" 라는 근거가 서야 정답입니다.

시각화로 "일찍 끝나는 순"의 효과를 본 뒤, 기본 정렬 그리디 → 구간 스케줄링 → 힙 결합형 순으로. 각 문제에서 "왜 이 기준인가"를 한 줄로 적는 연습을 하세요.