86 lines (54 loc) · 2.06 KB

그리디

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

그리디 문제 해결 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. 증명은 나중에

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