커리큘럼/페이즈 2 · 탐색의 기술
9주차

그리디

당장 최선인 선택이 전체 최선이 되는 경우 — 그리고 안 되는 경우.

개념

그리디는 지금 당장 가장 좋아 보이는 걸 집는 방식이에요. 뷔페에서 눈앞의 제일 맛있어 보이는 접시를 바로 집는 것과 같아요. 문제는, 지금 집은 게 나중에 후회를 만들지 않는다는 걸 보장할 수 있어야 한다는 거예요. 후회가 없다고 확신이 서면 그냥 집으면 되고(짧고 빠른 코드), 확신이 안 서면 모든 경우를 따지는 DP로 가야 해요. 그래서 그리디의 진짜 공부는 코드가 아니라 '이 선택이 후회 없는가'를 판단하는 눈이에요.그리디는 매 순간 가장 좋아 보이는 것을 고르고 뒤돌아보지 않는 방식이에요. 코드가 짧고 빨라요. 문제는 언제 이게 옳은가이고, 그것을 판단하는 것이 이번 주의 전부예요.

그리디가 통하려면

  • 탐욕 선택 속성 — 지금의 최선을 골라도 최적해를 놓치지 않는다
  • 최적 부분 구조 — 그 선택을 하고 남은 문제의 최적해를 더하면 전체 최적해가 된다
말은 어렵지만 실전에서 확인하는 방법은 단순해요. 반례를 먼저 찾아보는 것이에요. 5분 안에 반례가 안 나오면 그리디로 밀어붙이고, 반례가 나오면 DP로 가요. 증명하려 들면 시험 시간이 사라져요.

자주 나오는 형태

문제무엇을 기준으로 정렬왜
회의실 배정끝나는 시각 오름차순빨리 끝날수록 뒤에 남는 시간이 많다
구명보트무게 오름차순 + 양끝 포인터가장 무거운 사람은 가장 가벼운 사람과 짝지어야 이득
동전 거스름돈 (배수 화폐)큰 단위부터큰 단위가 작은 단위의 배수라 손해가 없다
최소 회의실 개수시작 시각 + 힙가장 빨리 끝나는 방을 재사용
회의실 배정에서 '시작이 빠른 것'이나 '짧은 것'을 고르면 왜 안 되는지 직접 반례를 그려 봐요. 긴 회의 하나가 짧은 회의 둘을 막는 그림이 바로 나와요. 이런 식으로 기준을 바꿔가며 반례를 찾는 연습이 그리디의 훈련법이에요.

직접 따라가 보기: 회의실 배정

회의 네 개가 있어요. 겹치지 않게 최대한 많이 잡는 게 목표예요. 끝나는 시각이 빠른 순으로 먼저 정렬해요. 빨리 끝날수록 뒤에 남는 시간이 많으니까요. 그다음 앞에서부터 하나씩 보면서, 마지막에 고른 회의가 끝난 시각(lastEnd) 이후에 시작하는 회의만 골라요.
끝나는 시각 오름차순으로 정렬한 뒤, 안 겹치는 것만 골라요
정렬 후 (끝나는 시각 기준)
  A  1 ~ 3
  B  2 ~ 5
  C  4 ~ 7
  D  6 ~ 8
​
lastEnd = -inf   (아직 아무것도 안 골랐어요)
​
A  시작 1 >= -inf ?  yes  ->  고름   lastEnd = 3
B  시작 2 >= 3    ?  no   ->  건너뜀
C  시작 4 >= 3    ?  yes  ->  고름   lastEnd = 7
D  시작 6 >= 7    ?  no   ->  건너뜀
​
고른 회의 = A, C   ->  최대 2개
B를 건너뛴 게 손해처럼 보여도, B를 골랐다면 lastEnd가 5가 돼서 C도 D도 못 잡아 오히려 하나만 남아요. 가장 빨리 끝나는 걸 고르는 선택이 뒤에 가장 넓은 자리를 남긴다는 게 이 그리디가 후회 없는 이유예요.

그리디가 깨지는 순간

이번 주의 마지막 문제가 이 지점이에요. 동전이 1, 5, 10처럼 배수 관계면 큰 것부터 집는 그리디가 맞아요. 그런데 동전이 1, 3, 4이고 6원을 만든다면?
  • 그리디: 4 + 1 + 1 = 3개
  • 최적: 3 + 3 = 2개
즉 그리디로 안 되는 문제란 '지금의 선택이 나중에 후회를 만드는' 문제예요. 후회를 없애려면 모든 선택지를 다 따져봐야 하는데, 그것을 중복 없이 하는 방법이 동적 계획법이에요.

패턴 코드

정렬 후 하나씩 집기 (회의실 배정)끝나는 시각 기준 정렬이 핵심. 시작 시각 기준으로 하면 틀려요.
javascript
meetings.sort((a, b) => a[1] - b[1]);
let count = 0;
let lastEnd = -Infinity;
for (const [start, end] of meetings) {
  if (start >= lastEnd) {
    count++;
    lastEnd = end;
  }
}
정렬 후 양끝에서 짝짓기 (구명보트)
javascript
people.sort((a, b) => a - b);
let i = 0;
let j = people.length - 1;
let boats = 0;
while (i <= j) {
  if (people[i] + people[j] <= limit) i++;
  j--;
  boats++;
}

이번 주 문제

이번 주 진행0 / 4
주차 진행률
이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.
프로그래머스 진행률
  • 체육복
    Lv. 1풀기
  • 조이스틱
    Lv. 2풀기
  • 큰 수 만들기
    Lv. 2풀기
  • 구명보트
    Lv. 2풀기
  • 단속카메라
    Lv. 3풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.
  1. 회의실 배정에서 '시작이 빠른 순'으로 고르면 안 되는 반례를 그릴 수 있는가?
  2. 동전 1, 3, 4로 6원을 만들 때 그리디가 왜 지는가?
  3. 그리디를 쓸지 DP를 쓸지 판단할 때 스스로에게 던지는 질문은 무엇인가?
  4. 회의실 배정에서 가장 빨리 끝나는 회의를 고르면 왜 뒤에 자리가 가장 많이 남나요?
← 8주차 · 투 포인터와 슬라이딩 윈도우10주차 · 스택 · 큐 · 덱 →