그리디

• "지금 당장 가장 좋은 선택"을 반복하면 전체적으로도 최적해가 된다는 아이디어
• 그리디는 "직관"과 "패턴 인식"이 중요
• 많은 문제를 풀어보면서 감을 익히는 것이 핵심

그리디 문제 해결 3단계

1. 선택 기준 정하기

• 무엇을 기준으로 "최선"을 판단할 것인가?
• 예: 끝나는 시간, 가치/무게 비율, 최소 비용

2. 정렬하기

• 대부분의 그리디는 정렬이 필요
• 선택 기준에 따라 오름차순/내림차순

3. 선택하고 검증하기

• 조건에 맞으면 선택, 안 맞으면 건너뛰기
• 선택한 것이 최적해인지 검증

자주 나오는 그리디 문제 유형

1. 활동 선택 문제

• 회의실 배정, 수업 시간표
• 핵심: 끝나는 시간 기준 정렬

2. 배낭 문제 (분할 가능)

• 가치/무게 비율로 정렬
• 비율이 높은 것부터 선택

3. 최소 비용 문제

• 최소 신장 트리, 다익스트라
• 가장 작은 비용부터 선택

4. 구간 관련 문제

• 겹치지 않는 구간 선택
• 구간 합치기

그리디 vs DP 구분하기

그리디가 가능한 경우:

• 현재의 선택이 미래에 영향 X
• 부분 최적해 = 전체 최적해
• 보통 O(n) 또는 O(n log n)

DP가 필요한 경우:

• 여러 경우를 비교해야 함
• 이전 선택이 다음 선택에 영향
• 보통 O(n²) 이상

그리디 문제 판별 팁

✅ 그리디 신호

• "가장 큰", "가장 작은", "최대", "최소"
• "~를 최대한 많이"
• 정렬하면 명확한 선택 기준이 보임

❌ 그리디 주의 신호

• 모든 경우를 확인해야 함
• 이전 선택을 번복해야 할 수도 있음
• 최적 부분 구조가 성립하지 않음

실전 접근법

1. 먼저 그리디로 접근해보기

• 직관적인 선택 기준 찾기
• 반례가 있는지 확인

2.반례가 있다면 DP 고려

• 그리디 실패 = 보통 DP 문제

3. 증명은 나중에

• 코딩 테스트에서는 직관이 중요
• 몇 가지 예시로 검증