그리디: 탐욕 선택과 반례

그리디란

매 순간 국소적으로 최선을 고르고, 되돌리지 않는 전략입니다.
항상 되지 않습니다. 증명 또는 강한 관례(문제 유형)가 있을 때 씁니다.

전형 패턴

반례 습관

그리디를 떠올리면 작은 반례를 먼저 만드세요.

• 동전이 1,3,4이고 금액 6일 때, 큰 단위만 고르면 실패할 수 있습니다.
• 구간을 시작점만으로 고르면 끝나는 시각 그리디보다 나쁜 해를 냅니다.

반례가 바로 나오면 DP·완전탐색·다른 정렬 키를 검토합니다.

DP와 경계

“모든 부분 문제의 최적해를 표로 쌓아야” 하면 DP입니다.
“한 번 스캔·한 번 정렬로 끝”이면 그리디 후보입니다.

복잡도

정렬이 들어가면 O(n log n), 아니면 O(n)인 경우가 많습니다.

연습

점프/구간/거스름 유형 중 쉬운 문제 하나에서,
1) 탐욕 규칙 한 줄 2) 반례 시도 3) 코드 순서로 적어 보세요.

체크리스트

1. 선택 규칙을 한 문장으로 말할 수 있는가?
2. 작은 반례로 Negate 시도했는가?
3. 정렬이 필요한가? 어떤 키인가?
4. 증명/유형이 익숙한가, 아니면 DP 후보인가?

한 줄

> 그리디는 빠르지만, 반례에 지면 바로 철수한다.

예: 점프 게임 감각

각 칸에서 “여기서 더 멀리 갈 수 있는가”만 갱신합니다.
뒤로 돌아가 다른 칸을 다시 고르지 않습니다. 그것이 그리디입니다.

반례가 떠오르지 않고, 도달 가능 범위가 단조 증가하면 이 유형일 가능성이 큽니다.

관련

그리디가 실패하면 DP 입문 레슨으로 넘어가세요.

더 깊게

읽은 뒤 연습장에서 예제 코드를 한 번 타이핑해 보세요. 눈으로만 보면 하루 뒤 사라집니다.

관련 원리 카드와 문제 태그로 바로 이어서 풀면, 문법·패턴이 한 묶음으로 남습니다.

막히면 30분 규칙: 입력을 로그로 확인 → 기대/실제 한 줄 비교 → 그래도 안 되면 배우기 레슨으로 잠시 복귀.