그리디 (Greedy)

관련 문제

문제	난이도	핵심
체육복	Lv.1	그리디 기초
큰 수 만들기	Lv.2	탐욕적 선택
구명보트	Lv.2	투 포인터 + 그리디

---

1. 개념

그리디(Greedy)는 매 순간 가장 좋아 보이는 선택을 반복해서 최적해를 구하는 방식이다.

DP처럼 이전 결과를 저장하거나, 브루트포스처럼 모든 경우를 탐색하지 않는다. 지금 이 순간 최선의 선택만 한다.

거스름돈 문제 — 890원을 최소 동전 개수로 거슬러줘야 할 때

500원 → 1개 (390원 남음)
100원 → 3개 (90원 남음)
 50원 → 1개 (40원 남음)
 10원 → 4개 (0원 남음)

총 9개 → 항상 큰 동전부터 선택하면 최소 개수가 보장된다

단, 그리디가 항상 최적해를 보장하지는 않는다. 문제에서 탐욕적 선택이 유효한지 먼저 판단해야 한다.

---

2. 동작 과정

체육복 — 여벌 옷이 있는 학생이 인접한 학생에게 빌려주는 경우

단계	처리
1	도난당한 학생 중 여벌이 있는 학생 제거 (자기가 입어야 하므로)
2	여벌 있는 학생 순서대로 왼쪽(i-1) 먼저 빌려주기
3	왼쪽에 못 빌려줬으면 오른쪽(i+1)에 빌려주기
4	체육 수업 들을 수 있는 학생 수 반환

왼쪽 먼저 빌려주는 것이 탐욕적 선택이다. 이렇게 해야 전체적으로 더 많은 학생이 수업을 들을 수 있다.

---

3. 핵심 사용 패턴

정렬 후 탐욕적 선택

그리디 문제는 대부분 정렬이 전제된다.

Arrays.sort(arr);  // 오름차순 정렬 후 탐욕적 선택

투 포인터와 결합

구명보트처럼 양 끝에서 좁혀오는 패턴이 자주 나온다.

int left = 0, right = arr.length - 1;
while (left < right) {
    if (arr[left] + arr[right] <= limit) {
        left++;  // 가벼운 사람도 태울 수 있으면 같이 태움
    }
    right--;  // 무거운 사람은 항상 태움
}

---

4. 핵심 포인트 2가지

탐욕적 선택이 유효한지 먼저 판단해라

그리디는 현재의 최선이 전체의 최선이 되어야 한다. 이게 성립하지 않으면 그리디로 풀 수 없다.

거스름돈: 큰 동전 먼저 → 항상 최적 ✅
배낭 문제: 가치/무게 비율 순 → 최적 아닐 수 있음 ❌ (DP 필요)

정렬 기준을 잘 잡아라

그리디에서 정렬 기준이 틀리면 답이 틀린다. 문제를 보고 어떤 기준으로 정렬해야 탐욕적 선택이 유효한지 먼저 생각해라.

// 구명보트: 몸무게 기준 오름차순
Arrays.sort(people);

// 큰 수 만들기: 앞에서부터 더 작은 수를 제거
// → 정렬보다 스택/탐욕적 제거 패턴 사용

---

5. 시간복잡도

유형	시간복잡도	비고
정렬 + 탐욕	O(N log N)	정렬이 병목
투 포인터 + 탐욕	O(N log N)	정렬 후 O(N) 탐색

그리디 자체는 O(N)이지만 정렬이 필요한 경우가 많아 O(N log N)이 된다.

---

6. 주의사항

• 그리디가 항상 최적해를 보장하지 않는다. 탐욕적 선택이 유효한지 먼저 증명하거나 확인해야 한다.
• 정렬 기준이 핵심이다. 어떤 기준으로 정렬하느냐에 따라 답이 달라진다.
• 여벌/도난 같은 예외 케이스를 먼저 처리해라. 체육복처럼 동일 학생이 여벌도 있고 도난도 당한 경우를 먼저 걸러야 한다.
• DP와 헷갈리지 마라. 현재 선택이 미래에 영향을 미치고 최적 부분 구조가 성립하면 그리디, 이전 결과를 참조해야 하면 DP다.