그리디 알고리즘 (Greedy Algorithm)

1. 개념

그리디 알고리즘은 매 순간 가장 좋아 보이는 선택(국소 최적) 을 해서 전체 문제의 최적해(전역 최적) 를 구하는 방식
즉, "당장 눈앞에서 가장 이득인 선택" 을 반복

• 장점: 구현이 간단하고 빠름 (O(n) ~ O(n log n) 수준)
• 단점: 항상 정답을 보장하지 않음 → 문제에서 그리디가 유효한 조건이 있는지 확인 필수

2. 그리디가 유효한 조건

1. 탐욕 선택 속성 (Greedy Choice Property)
   • 현재 선택이 이후의 선택에 영향을 주지 않고, 최적해의 일부가 될 수 있어야 함.
2. 최적 부분 구조 (Optimal Substructure)
   • 문제를 작은 부분 문제로 나눠도 그 해답이 전체 최적해의 일부여야 함.

즉, 부분에서의 최적이 전체에서도 최적이어야 한다는 것!
예: 거스름돈 문제(500·100·50·10원) → 큰 단위부터 거슬러도 항상 최소 개수

3. 기본 설계 패턴

패턴	설명	예시 문제
정렬 기반 선택	기준을 잡아 정렬 후, 앞/뒤에서부터 선택	회의실 배정, 가장 큰 수 만들기
우선순위 큐(Heap)	매번 최적의 값 추출	카드 정렬하기, N번째 큰 수
누적 합 / 차이	현재 상태 유지·갱신하며 진행	주식 최대 이익, 로프 문제
투 포인터	정렬 + 양쪽 끝 포인터 이동	두 용액, 수 묶기
카운팅/그룹핑	빈도·그룹 기준으로 최적 선택	문자열 재정렬, 만들 수 없는 금액

4. 자주 쓰이는 연산 & 기법

① 정렬

그리디 문제의 80%는 정렬이 핵심.

Arrays.sort(arr); // 오름차순
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순

② 우선순위 큐

항상 최솟값·최댓값을 빠르게 꺼내야 할 때.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

③ 누적 합

값을 하나씩 더하거나 빼면서 최적 조건 갱신.

int sum = 0, answer = 0;
for (int x : arr) {
    sum += x;
    answer = Math.max(answer, sum);
}

④ 투 포인터

양 끝에서 탐색, 중간에서 조건 만족 시 갱신.

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum > target) right--;
    else left++;
}

⑤ 그리디 + 정렬 기준 커스터마이징

Arrays.sort(meetings, (a, b) -> {
    if (a[1] == b[1]) return a[0] - b[0];
    return a[1] - b[1];
});

 

5. 대표 유형 & 예제

유형	설명	예시
거스름돈 문제	큰 단위부터 거슬러줌	동전 0 (백준 11047)
회의실 배정	종료 시간이 빠른 순	백준 1931
로프 문제	강한 로프부터 고려	백준 2217
주식 최대 이익	최소값 갱신하며 최대 차이 계산	LeetCode Best Time to Buy and Sell Stock
카드 정렬하기	작은 카드 묶음부터 합치기	백준 1715
만들 수 없는 금액	작은 값부터 누적 합으로 불가능 값 탐색	백준 2437
배	무거운 화물부터 큰 배에 배정	백준 1092

6. 시간 복잡도 분석

• 정렬 기반: O(n log n)
• 우선순위 큐 기반: O(n log n)
• 단순 순회 기반: O(n)
• 투 포인터: O(n) (정렬이 포함되면 O(n log n))

7. 실전 팁

1. "정렬"이 떠오르면 그리디일 가능성↑
2. "가장 큰/작은 값부터"라는 조건이 나오면 → 우선순위 큐 or 정렬
3. 부분 최적이 전체 최적인지 꼭 검증
4. 반례 생각하기: 간단한 예로 깨지면 DP나 완전탐색 고려