[그리디 알고리즘 (Greedy)]

코딩테스트 스터디 7주차 학습 자료를 정리한 글이다.

매 순간 가장 좋아 보이는 선택을 반복해 전체 최적해를 구하는 방식과, 이분 탐색과 결합해 최적값을 검증하는 패턴을 다룬다.

---

1. 그리디 알고리즘

그리디란

그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방식이다. 미래를 고려하지 않고 현재 상태에서 최적인 선택을 반복한다.

편의점에서 잔돈을 거슬러줄 때와 같은 원리다. 1000원을 거슬러줘야 한다면, 500원짜리를 먼저 최대한 사용하고, 그다음 100원, 50원, 10원 순서로 처리한다. 매 단계에서 가능한 큰 동전을 선택하는 것이 결국 최소 개수의 동전으로 이어진다.

그런데 이 전략이 항상 옳은 것은 아니다. 동전 종류에 따라 그리디가 실패하는 경우도 있다. 그것이 그리디와 DP를 구분하는 핵심이다.

그리디가 성립하는 조건

그리디가 최적해를 보장하려면 두 가지 성질이 성립해야 한다.

탐욕적 선택 속성 (Greedy Choice Property)
현재 최적의 선택이 전체 최적해에 포함된다. 즉, 지금 선택한 것을 나중에 번복하지 않아도 된다.

최적 부분 구조 (Optimal Substructure)
전체 문제의 최적해가 부분 문제의 최적해로 구성된다.

이 두 성질이 성립한다는 것을 증명하지 못한다면, 그리디로 풀었더라도 반례가 존재할 수 있다.

그리디 vs DP

구분	그리디	DP
선택 방식	현재 최적 선택만 고려	모든 경우를 기록하고 비교
시간 복잡도	보통 O(n log n) 이하	보통 O(n²) 이상
정확성 보장	특정 조건 하에서만	항상 최적해
구현 난이도	비교적 단순	점화식 설계 필요
적용 예시	활동 선택, 거스름돈	배낭, LCS, 최장 증가 부분수열

그리디가 통하는 문제는 보통 정렬 후 한 번의 순회로 풀린다. DP는 선택지를 모두 기록해야 하므로 메모리와 시간이 더 필요하지만, 최적해를 항상 보장한다.

그리디 함정: 항상 최적이 아닌 경우

동전 종류가 [500, 400, 100]이고 800원을 거슬러야 한다면:

그리디 — 4개 500 + 100 + 100 + 100 = 4개 500원부터 최대한 사용하는 그리디 전략

최적 — 2개 400 + 400 = 2개 단위가 배수 관계가 아니면 DP 사용

---

2. 그리디 대표 패턴

활동 선택 문제

N개의 활동이 있고 각 활동은 시작 시간과 끝 시간을 가진다. 한 번에 하나의 활동만 할 수 있을 때 최대한 많은 활동을 선택하는 문제다.

끝 시간 기준으로 정렬 후 순서대로 선택하는 것이 핵심이다. 끝나는 시간이 빠른 활동을 선택할수록, 다음 활동을 위한 여유 시간이 더 많이 남기 때문이다.

활동: [(1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11), (8,12), (2,13), (12,14)] 끝시간 정렬 후 선택: - (1,4): 선택, last_end=4 - (3,5): 5 > 4, 선택, last_end=5 - (5,7): 7 > 5, 선택, last_end=7 - (8,11): 11 > 7, 선택, last_end=11 - (12,14): 14 > 11, 선택, last_end=14 총 5개 선택

def activity_selection(activities): activities.sort(key=lambda x: x[1]) count = 1 last_end = activities[0][1] for start, end in activities[1:]: if start >= last_end: count += 1 last_end = end return count

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)] print(activity_selection(activities))

출력:

5

회의실 배정

회의실 배정은 활동 선택과 동일한 원리다. 회의가 끝나는 시간 기준으로 정렬하고, 이전 회의가 끝난 이후에 시작하는 회의를 그리디하게 선택한다.

def meeting_room(meetings): meetings.sort(key=lambda x: (x[1], x[0])) count = 0 last_end = 0 for start, end in meetings: if start >= last_end: count += 1 last_end = end return count

끝 시간이 같다면 시작 시간이 빠른 순서로 정렬한다. 시작 시간이 last_end와 같은 경우도 선택 가능하므로 start >= last_end 조건임에 주의한다.

최소 동전 개수 (배수 관계 보장)

동전 단위가 [1, 5, 10, 50, 100, 500]처럼 큰 단위가 작은 단위의 배수인 경우, 그리디가 최적해를 보장한다.

def min_coins(amount, coins): coins.sort(reverse=True) count = 0 for coin in coins: count += amount // coin amount %= coin return count

coins = [1, 5, 10, 50, 100, 500] print(min_coins(1260, coins))

출력:

6

1260원 = 500×2 + 100×2 + 50×1 + 10×1 = 6개.

거스름돈 (대표 그리디)

위의 최소 동전 문제와 동일한 구조다. 단위가 배수 관계이면 그리디가 성립하고, 그렇지 않으면 DP로 풀어야 한다.

---

3. 이분 탐색 + 그리디 결합 패턴

이분 탐색과 그리디는 자주 함께 사용된다. 특히 "N개를 K개의 그룹으로 나눌 때 최대/최솟값 최적화" 류의 문제에서 결합된다.

전형적인 패턴은 세 단계로 구성된다.

1. 정답이 될 수 있는 값의 범위를 설정한다

최솟값과 최댓값으로 이분 탐색의 시작 범위를 정한다

2. 그 범위에 이분 탐색을 적용한다

mid 값을 정답 후보로 놓고 조건 확인 함수를 호출한다

3. 특정 값이 정답이 될 수 있는지 그리디로 확인한다

탐욕적으로 선택해 나가면서 조건 충족 여부를 O(n)에 판별한다

이분 탐색이 "어느 값이 정답인가"를 좁혀가고, 그리디가 "이 값이 정답이 될 수 있는가"를 빠르게 판별하는 구조다.

예시: 배열을 K개 구간으로 나눌 때 구간 합 최댓값 최소화

배열을 K개의 연속 구간으로 나눌 때 각 구간 합의 최댓값을 최소화하는 문제다.

• 이분 탐색: 정답(최댓값의 최솟값)의 범위 [max(arr), sum(arr)]에 적용
• 그리디: 특정 최댓값 mid로 나눌 때 K개 이하로 나눌 수 있는지 탐욕적으로 확인

def can_divide(arr, k, limit): groups = 1 current_sum = 0 for num in arr: if num > limit: return False if current_sum + num > limit: groups += 1 current_sum = num else: current_sum += num return groups <= k def min_max_partition(arr, k): left, right = max(arr), sum(arr) answer = right while left <= right: mid = (left + right) // 2 if can_divide(arr, k, mid): answer = mid right = mid - 1 else: left = mid + 1 return answer

arr = [1, 2, 3, 4, 5] k = 2 print(min_max_partition(arr, k))

출력:

9

[1,2,3]과 [4,5]로 나누면 최댓값은 9. [1,2,3,4]와 [5]로 나누면 최댓값은 10. 9가 최소다.

---

4. 시간 복잡도 정리

패턴	시간 복잡도	비고
활동 선택	O(n log n)	정렬이 병목
거스름돈	O(k)	k: 동전 종류 수
파라메트릭 서치 + 그리디	O(log(범위) × n)
배낭(그리디 불가, DP 필요)	O(nW)

---

5. Python 자주 쓰는 메서드

sorted -- 기준에 따른 정렬

그리디 문제에서 정렬 기준 설정이 핵심인 경우가 많다. key와 reverse 파라미터로 다양한 기준을 표현한다.

meetings = [(3, 5), (1, 4), (5, 7), (0, 6)] by_end = sorted(meetings, key=lambda x: x[1]) print(by_end) by_end_then_start = sorted(meetings, key=lambda x: (x[1], x[0])) print(by_end_then_start)

출력:

[(1, 4), (3, 5), (0, 6), (5, 7)] [(1, 4), (3, 5), (0, 6), (5, 7)]

key에 튜플을 사용하면 다중 기준 정렬이 가능하다. 첫 번째 기준이 같을 때 두 번째 기준으로 정렬한다.

heapq -- 우선순위 기반 선택

매 단계에서 최소(또는 최대) 값을 선택하는 그리디에서 힙을 사용한다. Python의 heapq는 최솟값 힙이다.

import heapq items = [5, 1, 3, 2, 4] heap = [] for item in items: heapq.heappush(heap, item) print(heapq.heappop(heap)) print(heapq.heappop(heap)) print(heapq.heappop(heap))

출력:

1 2 3

최댓값 힙이 필요하면 값에 -1을 곱해서 넣고, 꺼낼 때 다시 -1을 곱한다.

sum, enumerate, zip

그리디에서 자주 쓰이는 내장 함수다.

weights = [10, 20, 30] values = [60, 100, 120] total_weight = sum(weights) print(total_weight) for i, (w, v) in enumerate(zip(weights, values)): print(f"아이템 {i}: 무게={w}, 가치={v}, 단위가치={v/w:.1f}")

출력:

60 아이템 0: 무게=10, 가치=60, 단위가치=6.0 아이템 1: 무게=20, 가치=100, 단위가치=5.0 아이템 2: 무게=30, 가치=120, 단위가치=4.0

enumerate는 인덱스와 값을 동시에 순회하고, zip은 두 리스트를 병렬로 묶는다. 분수 배낭 문제처럼 단위 가치를 계산해 정렬할 때 이 조합이 유용하다.

min / max with key

단순한 최솟값, 최댓값이 아니라 특정 기준으로 최적 원소를 선택할 때 key를 사용한다.

tasks = [('A', 5), ('B', 2), ('C', 8), ('D', 1)] shortest = min(tasks, key=lambda x: x[1]) longest = max(tasks, key=lambda x: x[1]) print(shortest) print(longest)

출력:

('D', 1) ('C', 8)

전체 리스트를 정렬하지 않고 O(n)에 기준에 맞는 원소를 바로 선택한다.

---

6. 연습 문제

문제	난이도	링크	핵심 접근
큰 수 만들기	Lv 2	프로그래머스	스택 그리디, k개 제거 후 최대 수
구명보트	Lv 2	프로그래머스	그리디 + 투 포인터, 가장 무거운 사람과 가장 가벼운 사람 조합
조이스틱	Lv 2	프로그래머스	그리디, 최소 이동 횟수 탐색
단속카메라	Lv 3	프로그래머스	끝 지점 기준 정렬 후 그리디 선택