그리디 알고리즘 | 매 순간 최선 탐욕 알고리즘 완벽 정리
이 글의 핵심
그리디는 지역 최선이 전역 최적과 맞닿을 때 강력합니다. 탐욕 선택·최적 부분 구조, 교환 논법(회의·분할 배낭·SJF), DP와의 분기, 실패 패턴, 프로덕션 휴리스틱까지 예제와 함께 정리합니다.
시리즈 안내
들어가며
탐욕법은 구현은 쉬워 보여도 최적성이 맞는지 증명하지 않으면 잘못된 답을 낼 수 있습니다. 이 글에서는 전형적인 그리디 패턴을 익히고, 언제 DP나 다른 전략으로 넘어가야 하는지 감을 잡을 수 있습니다.
”매 순간 최선의 선택이 최적해?”
그리디 알고리즘은 매 순간 최선의 선택을 합니다. 항상 최적해를 보장하지는 않지만, 증명 가능한 경우 매우 효율적입니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다.
코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 그리디 알고리즘이란?
개념
그리디(탐욕) 알고리즘은 현재 단계에서 보이는 지역 최선만 고릅니다. 아래는 큰 단위 동전부터 최대한 많이 쓰는 거스름돈 예시입니다. 단, 동전 액면가가 임의이면 그리디가 최소 개수를 보장하지 않을 수 있으므로, 문제에서 그리디가 성립하는지(교환·정렬 조건 등)를 확인해야 합니다.
다음 Python 예제 코드입니다.
# 예: 거스름돈 (500, 100, 50, 10원)
# 1260원 거슬러주기
coins = [500, 100, 50, 10]
change = 1260
count = 0
for coin in coins:
count += change // coin # 최대한 많이
change %= coin
print(count) # 6 (500*2 + 100*2 + 50*1 + 10*1)그리디 vs DP
| 특징 | 그리디 | DP |
|---|---|---|
| 선택 | 현재 최선 | 모든 경우 고려 |
| 시간복잡도 | O(n log n) | O(n²) ~ O(2ⁿ) |
| 최적해 보장 | X (증명 필요) | O |
| 구현 | 간단 | 복잡 |
2. 대표 문제
문제 1: 회의실 배정
def max_meetings(meetings):
"""
최대한 많은 회의 배정
[(시작, 끝), ...]
"""
# 끝나는 시간 기준 정렬
meetings.sort(key=lambda x: x[1])
count = 0
last_end = 0
for start, end in meetings:
if start >= last_end:
count += 1
last_end = end
return count
# 테스트 (끝 시각 기준 정렬 후 그리디)
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings)) # 2
meetings3 = [(1, 4), (2, 5), (3, 6), (7, 8), (8, 9)]
print(max_meetings(meetings3)) # 3
meetings2 = [(1, 2), (3, 4), (5, 6), (7, 8)] # 서로 안 겹침
print(max_meetings(meetings2)) # 4문제 2: 동전 거스름돈
def min_coins(coins, amount):
"""
최소 동전 개수
"""
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount >= coin:
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# 테스트
coins = [500, 100, 50, 10]
print(min_coins(coins, 1260)) # 6
# ❌ 그리디 실패 예
coins = [10, 7, 1]
amount = 14
# 그리디: 10 + 1 + 1 + 1 + 1 = 5개
# 최적: 7 + 7 = 2개 (DP 필요!)문제 3: 큰 수 만들기
def make_largest_number(number, k):
"""
숫자 k개를 제거해서 가장 큰 수 만들기
"1924", k=2 → "94"
"""
stack = []
removed = 0
for digit in number:
# 스택 top이 현재보다 작으면 제거
while stack and removed < k and stack[-1] < digit:
stack.pop()
removed += 1
stack.append(digit)
# 아직 k개 안 지웠으면 뒤에서 제거
return ''.join(stack[:len(stack) - (k - removed)])
# 테스트
print(make_largest_number("1924", 2)) # "94"
print(make_largest_number("1231234", 3)) # "3234"문제 4: 쿠키 나눠주기 (아이·욕심쟁이 정렬)
아이의 욕심과 쿠키 크기가 주어질 때, 최대 몇 명에게 나눠줄 수 있는지 구합니다. 쿠키·아이 모두 오름차순으로 두고, 작은 쿠키부터 “가장 욕심이 작은 아이”에게 맞추면 됩니다. “지금 줄 수 있는 가장 작은 쿠키로 가장 작은 욕싱을 채운다”는 탐욕이 전역 최대 인원과 맞습니다.
def find_content_children(greed, size):
g = sorted(greed)
s = sorted(size)
i = j = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]:
i += 1
j += 1
return i문제 5: 화살로 풍선 터뜨리기 (구간 끝 정렬)
각 풍선은 [start, end] 구간으로 표현됩니다. 화살은 y좌표에 수직으로 날아가며, 구간을 한 번에 관통하면 터집니다. 구간 끝점 기준 정렬 후, 현재 화살 위치보다 start가 크면 새 화살을 쏩니다. 회의실 배정과 같은 “끝을 기준으로 압축” 패턴입니다.
def find_min_arrow_shots(points):
points.sort(key=lambda x: x[1])
ans = 0
end = None
for s, e in points:
if end is None or s > end:
ans += 1
end = e
return ans문제 6: 구간 병합 (시작 시각 정렬 + 스윕)
겹치는 구간을 병합합니다. 시작 시각으로 정렬한 뒤, 이전 병합 구간과 겹치면 끝만 갱신하고, 아니면 새 구간을 추가합니다.
def merge(intervals):
intervals.sort(key=lambda x: x[0])
out = [intervals[0][:]]
for s, e in intervals[1:]:
if s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out문제 7: 점프 게임 (도달 가능 / 최소 점프)
LeetCode 55(도달 가능 여부): 각 칸의 값만큼 앞으로 점프할 수 있을 때 마지막에 도달할 수 있나요? 가장 멀리 갈 수 있는 인덱스를 추적하는 그리디입니다. 인덱스 i에서 i + nums[i]가 지금까지의 최대 도달 거리를 넘기면 갱신하고, 어느 순간 i가 최대 도달 거리를 넘으면 불가능입니다.
def can_jump(nums):
reach = 0
for i, x in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + x)
return TrueLeetCode 45(최소 점프 횟수): “이번 점프 구간 안에서 다음 점프로 가장 멀리 갈 수 있는 지점”을 고르는 BFS/그리디 혼합이 전형적입니다. end는 “현재 점프 횟수로 도달 가능한 구간의 끝”, 그 안에서 다음 구간의 최대 도달 far를 갱신합니다.
def jump_min_steps(nums):
if len(nums) <= 1:
return 0
jumps = end = far = 0
for i in range(len(nums) - 1):
far = max(far, i + nums[i])
if i == end:
jumps += 1
end = far
return jumps문제 8: 주유소 (원형, 단일 출발)
gas[i]만큼 넣고 cost[i]만큼 다음까지 갑니다. 총 가스 ≥ 총 비용이면 해가 존재하고, 그때 한 번의 선형 스캔으로 시작 인덱스를 찾을 수 있습니다. 누적 잔량이 음수가 되는 지점에서는 그 구간의 어떤 점을 출발해도 도달 전에 떨어지므로, 다음 인덱스를 새 후보 출발지로 잡는 탐욕이 성립합니다.
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
start = tank = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return start문제 9: 두 도시 예산 (정렬 키 하나로 편차 흡수)
2n명을 두 도시에 n명씩 보낼 때 비용 합을 최소화합니다. 각 사람에 대해 costA - costB를 보면, A를 택했을 때의 “추가 비용”입니다. 차이가 작은 순으로 A에 보내고, 나머지는 B로 보내는 식으로 정렬 키(차이) 그리디가 최적입니다.
def two_city_scheduling(costs):
# costs[i] = [toA, toB]; A에 보낼 때의 추가비용 순으로 정렬
diff = sorted(costs, key=lambda c: c[0] - c[1])
n = len(costs) // 2
return sum(c[0] for c in diff[:n]) + sum(c[1] for c in diff[n:])문제 10: 분할 배낭 (가치/무게 비율)
0-1 배낭이 아니라 “쪼갤 수 있는” 물건이면, 단위 무게당 가치가 큰 순으로 담으면 최적입니다. 구현은 정렬 후 남은 용량만큼 잘라 담으면 됩니다. (아래는 교환 논법으로 최적성이 증명되는 대표 케이스입니다.)
def fractional_knapsack(items, capacity):
# items: (value, weight)
items = sorted(items, key=lambda x: x[0] / x[1], reverse=True)
total = 0.0
for v, w in items:
if capacity <= 0:
break
take = min(w, capacity)
total += v * (take / w)
capacity -= take
return total3. 최적 부분 구조와 탐욕 선택 속성
그리디가 최적해를 보장하려면, 보통 아래 두 가지를 동시에 만족함을 보입니다. (문제마다 정식화는 다르지만, 사고의 뼈대는 동일합니다.)
최적 부분 구조 (Optimal Substructure)
정의(직관). 한 번 탐욕적으로 선택한 뒤 남은 부분 문제에 대해서도, 전체 최적해를 이루는 해가 부분 문제의 최적해로 이어진다는 성질입니다. 다시 말해, “첫 선택을 올바르게 고른 뒤에는, 남은 입력에 대해 같은 목적 함수를 최적화하는 하위 문제”로 쪼갤 수 있어야 합니다.
DP와의 공통점은 “부분 문제로 나눈다”는 점이지만, 그리디는 후보를 한 방향으로 줄여 나가며 보통 더 가벼운 결정 구조를 갖습니다. 반면 부분 문제 간에 순서가 바뀌면 비용이 달라지는 형태(배낭의 일반 버전 등)에서는 최적 부분 구조만으로 부족하고, 그리디가 실패하는 경우가 많습니다.
탐욕 선택 속성 (Greedy Choice Property)
정의(직관). 어떤 최적해가 존재할 때, 그 최적해가 반드시 포함할 수 있는 “지금 단계의 탐욕적 선택”이 존재한다는 주장입니다. 즉, 국소 최선을 한 번 해도 전체 최적해를 망치지 않는 첫 수가 있다는 뜻입니다.
이 두 성질을 모두 보이면, 흔히 다음 형태의 귀납적 논리로 “그리디가 최적”이라고 말할 수 있습니다.
- 탐욕 선택 속성: 첫 선택을 탐욕 규칙대로 해도 어떤 최적해와 호환된다.
- 최적 부분 구조: 그 선택을 고정한 뒤의 부분 문제에 대해서도 같은 방식의 탐욕이 통한다.
4. 교환 논법 (Exchange Argument)
교환 논법은 탐욕 선택 속성을 증명할 때 가장 많이 쓰는 기법입니다. 흐름은 다음과 같습니다.
- 임의의 최적해 O를 가정한다.
- O의 첫 선택이 탐욕 선택 g와 다르면, 원소를 맞바꾸거나 교체하여 O를 O′로 바꾼다.
- O′ 역시 최적해(또는 최적해와 같은 목적 함수값)이면서, 첫 선택이 g와 일치하도록 만든다.
- 같은 방식으로 귀납적으로 반복하거나, 부분 문제로 넘어가 최적 부분 구조를 적용한다.
핵심은 “탐욕 선택으로 바꿔도 목적 함수가 나아지지 않고(혹은 동일), 제약을 위반하지 않는다”는 점을 보이는 것입니다.
예: 회의실 배정 — 끝 시각이 가장 이른 회의를 택하는 전략
회의 i를 (s_i, f_i)로 두고, 종료 시각 f_i 오름차순으로 정렬한 뒤, 이전에 고른 회의가 끝난 시각 이후에 시작하는 회의만 택합니다.
교환 논법 스케치. 임의 최적해가 첫 회의로 (s, f)를 택하고, 탐욕이 (s_g, f_g)를 택한다고 하면, 정렬에 의해 f_g ≤ f입니다. (s, f) 대신 (s_g, f_g)를 넣어도, 이후에 배치 가능한 회의 집합은 늘어나지 않고(더 일찍 끝나므로) 줄지도 않는 방향으로만 바뀝니다. 구체적으로는, f_g ≤ f이므로 “다음 회의를 넣을 수 있는 시작 시각”의 여유가 탐욕 쪽이 더 크거나 같습니다. 따라서 최적해의 첫 회의를 탐욕 선택으로 바꿔도 회의 개수는 유지할 수 있고, 귀납적으로 전체가 탐욕해와 동일한 개수를 달성할 수 있음을 보일 수 있습니다.
코드로는 앞 절의 max_meetings가 그대로 이 정책의 구현입니다. 여기서 중요한 것은 “정렬 키(종료 시각)가 교환 논법의 부등식을 담고 있다”는 점입니다.
귀류법과의 관계
귀류법은 “탐욕이 최적이 아니다”라고 가정해 모순을 찾는 방식입니다. 교환 논법이 구성적으로 최적해를 탐욕해로 변형한다면, 귀류법은 부정적으로 불가능성을 밀어붙이는 경우가 많습니다. 난이도가 비슷한 문제에서는 둘 중 편한 쪽을 택하면 됩니다.
귀류법 스케치
- 그리디가 만든 해의 값이 최적보다 나쁘다고 가정
- 그 차이를 만드는 “첫으로 다른 선택”을 잡고, 교환 논법 또는 불변식으로 모순 유도교환 논법: 분할 배낭 (단위 가치 순)
최적해가 탐욕(비율 큰 물건부터)과 다르다고 하면, 어딘가에서 더 비싼 단위가 뒤로 밀린 두 물건 A(단위 가치 높음), B(낮음)가 존재합니다. 용량이 허용하는 한 A와 B의 할당량을 서로 맞바꾸면 (A를 조금 더, B를 조금 덜) 총 가치는 늘지 않고 줄지도 않는데, 목적이 최대화이면 엄밀히는 “늘어나는 방향으로” 교환할 수 있어 모순입니다. 즉, 최적해를 탐욕해로 변형할 수 있어 비율 정렬 그리디가 최적입니다.
교환 논법: ATM 대기 시간 합 최소 (SJF)
n명의 작업 시간 t_i가 있고, 한 대의 ATM에서 순서를 정해 대기 시간 합을 최소화할 때 짧은 작업 먼저(SJF)가 최적입니다. 두 최적 순열에서 인접한 두 작업 (a, b)의 순서를 바꿨을 때 대기 시간 합 변화는 t_a - t_b에 비례하는 항으로 정리되므로, t_a > t_b이면 바꾸는 편이 유리합니다. 따라서 오름차순 정렬이 유일한 최적 순서가 됩니다.
def atm_total_time(times):
"""백준 11399: 정렬 후 누적 시간의 합"""
times.sort()
acc = total = 0
for t in times:
acc += t
total += acc
return total(문제마다 “대기 시간”에 자기 처리 시간을 포함할지 여부가 다르니, 누적 합의 합인지 확인 후 구현합니다.)
교환 논법: 중복 없는 회의 최대 개수와 “끝 시각” 정렬
앞서 회의실 배정에서 쓴 스케치를 한 단계 더 밀면, 임의 최적해의 첫 회의를 탐욕 선택(가장 이른 종료)으로 바꿔도 포함 가능한 남은 회의 집합은 축소되지 않는다는 점이 핵심입니다. f가 더 늦게 끝나는 회의를 탐욕 회의로 바꾸면, 다음에 넣을 수 있는 시작 시각의 여유가 늘거나 같아지므로 교환이 항상 안전합니다.
5. 매트로이드 이론 기초: 그리디가 “정답”인 대표 구조
모든 그리디 문제가 매트로이드로 설명되지는 않지만, “가중치 합을 최대화하는 독립 집합” 문제의 상당수는 매트로이드 구조 위에서 그리디가 최적임이 정리로 보장됩니다.
정의: 매트로이드
유한 집합 E와, E의 부분 집합들 가운데 허용되는 집합들의 모임 I(독립 집합 족)이 다음을 만족할 때 (E, I)를 매트로이드라고 합니다.
- 유효성(비어 있지 않음): ∅ ∈ I
- 유전성(Hereditary): A ∈ I이고 B ⊆ A이면 B ∈ I
- 교환성(Independent set exchange): A, B ∈ I이고 |A| < |B|이면, B에만 있고 A에는 없는 원소 e가 존재하여 A ∪ {e} ∈ I
직관적으로는 “제약이 잘 정의된 독립 집합들”이며, 3번이 “조금 더 큰 독립 집합으로 점진적으로 확장할 수 있다”는 구조를 줍니다.
가중치 그리디 정리 (요지)
각 원소 e ∈ E에 비음수 가중치 w(e)가 있을 때, 가중치가 큰 순서대로 원소를 보며 “지금까지 고른 집합에 추가했을 때 여전히 독립이면 추가”하는 그리디는 가중치 합이 최대인 독립 집합을 찾습니다.
대표 예는 다음과 같습니다.
- 최소 신장 트리(크루스칼): 간선 집합이 사이클을 만들지 않으면 독립인 구조(그래프 매트로이드의 숲) 위에서, 최소화 문제로는 가중치 오름차순으로 같은 논리가 성립합니다.
- 일부 스케줄링/매칭 변형: 독립 조건이 매트로이드로 표현되면 동일한 그리디 해석이 가능합니다.
주의: 모든 그리디가 매트로이드는 아님
예를 들어 구간 스케줄링(회의실 배정)은 매우 유명한 그리디이지만, “최대 크기의 독립 집합”을 다루는 방식이 위 정의의 매트로이드와 바로 일치하지 않는 서술이 필요한 경우가 있습니다(문제를 매트로이드 교차 등으로 일반화하면 다른 관점이 열리기도 합니다). 실무·코테에서는 “매트로이드니까 맞다”로 끝내기보다, 문제를 매트로이드로 모델링할 수 있는지부터 확인하는 편이 안전합니다.
6. 그리디 vs DP 의사결정 가이드
표로 요약한 뒤, 실전에서의 분기를 문장으로 고정해 두면 설계 회의에서 설득력이 생깁니다.
한눈에 비교
| 관점 | 그리디 | DP |
|---|---|---|
| 결정 | 지금 보이는 최선 한 번 | 상태별로 이전 결과를 재사용 |
| 시간 | 대개 (O(n \log n)) 전후 (정렬·힙) | (O(n^2))~지수, 상태 수에 좌우 |
| 최적 보장 | 문제 구조가 허용할 때만 | 정의만 맞으면 보통 보장 |
| 구현 난이도 | 짧고 직관적 | 점화식·초기값·순서 설계 필요 |
이렇게 보면 DP 쪽이 유리한 신호
- 이전 선택이 이후 비용 전체를 바꾼다(순서 의존, 상호작용 강함).
- 지역 최선이 명백한 반례가 작은 입력에서 바로 나온다.
- 문제가 “최대/최소”이지만 제약이 2차원 이상으로 얽혀 있고, 한 번의 정렬 키로 줄어들지 않는다.
- 0-1 배낭, 편집 거리, LIS의 (O(n^2)) 형태처럼 알려진 DP 테이블 구조가 떠오른다.
이렇게 보면 그리디 후보인 신호
- 정렬 한 번으로 “처리 순서”가 확정되고, 그 순서가 불변식으로 유지된다.
- 교환 논법으로 “첫 선택을 탐욕으로 바꿔도 손해가 없다”는 스케치가 바로 나온다.
- 매트로이드·분할 배낭·구간 스케줄링 등 증명된 템플릿과 형태가 같다.
- 제약이 “지금까지의 합/최대 도달 거리”처럼 스칼라 한두 개로 압축된다(점프 게임, 주유소).
권장 워크플로
- 작은 예제로 그리디·완탐(또는 DP) 결과를 맞춰 본다.
- 그리디가 맞다면 “탐욕 선택 속성” 문장을 한 줄로 쓴다.
- 반례가 떠오르면 상태 정의를 적어 DP로 전환한다.
7. 실패하는 그리디 패턴 (반례 루트)
그리디는 “같아 보이는데 다른 문제”에서 자주 무너집니다. 패턴을 외우기보다 왜 깨지는지를 기억하는 편이 낫습니다.
1) 0-1 배낭 vs 분할 배낭
분할은 단위 가치 순이 최적이지만, 0-1은 “지금 가장 좋아 보이는 물건”이 나중 선택을 망가뜨립니다. 전형적으로 DP 또는 분기한정.
2) 임의 동전 액면
액면이 임의이면 최소 개수 동전 문제는 그리디가 틀릴 수 있습니다(앞선 예: 14원을 10+1×4로). BFS(금액을 상태로) 또는 DP가 안전합니다.
3) 최장 경로·일반 TSP
지역적으로 이어 보이는 간선을 고르면 전체가 최장이 되지 않습니다. DAG 최장 경로는 DP, 일반 그래프는 NP-난해에 가깝습니다.
4) 집합 덮기(Set Cover)의 순수 그리디
“아직 안 덮인 원소를 가장 많이 덮는 집합부터” 같은 그리디는 근사로는 쓰이지만 최적해를 보장하지 않습니다. 요구가 “최소 개수의 최적”이면 ILP·정확 알고리즘이 필요할 수 있습니다.
5) “최근접 이웃” TSP 휴리스틱
실무에서 빠른 경로를 낼 때 쓰지만 최적이 아님이 전제입니다. 코테에서 최적을 요구하면 실패합니다.
6) 작업 스케줄링의 데드라인·패널티 혼합
단순 SJF만으로 끝나지 않는 변형(지연 패널티, 가중치, 선후관계)에서는 그리디 실패 → 우선순위 큐 DP·최소 비용 유량 등으로 넘어가는 경우가 많습니다.
요약: “한 번 고르면 남은 문제의 형태가 동일한 부분 문제로 쪼개지는가?”에 아니오가 나오면 그리디를 의심합니다.
8. 프로덕션에서의 그리디 패턴
알고리즘 교재의 그리디와 실무의 그리디는 한결같이 “매 단계의 휴리스틱”이지만, 운영 환경에서는 증명된 전형 문제보다 제약이 더 많고 측정이 필수입니다.
자주 등장하는 형태
- 우선순위 큐 + 제한 자원 할당: 요청을 데드라인·가중치 순으로 처리하며, 자원이 비는 즉시 다음 작업을 배정하는 방식. 스케줄러·작업 큐·로드 밸런싱의 일부 휴리스틱이 여기에 가깝습니다.
- 정렬 후 선형 스윕: 구간 겹침, 스케줄 충돌 검사, 타임라인 합병 등은 “정렬 키를 무엇으로 둘지”가 설계의 핵심입니다.
- 그리디 근사 + 온라인 판단: 캐시를 채울 공간이 부족할 때의 휴리스틱, 라우팅의 일부 결정 등은 최적해 대신 합리적 하한·상한 내에서 빠른 결정을 목표로 합니다.
엔지니어링 체크리스트
- 반례 검색: 작은 입력·랜덤 대 소수 비교(느리지만 맞는 기준 구현, 또는 ILP/작은 완탐)로 그리디와 검증합니다.
- 불변식 기록: “정렬 이후 스택이 단조”, “누적 합이 항상 ≤ 예산”처럼 루프 불변식을 문장으로 적어 둡니다.
- 회귀 테스트: 제약이 바뀌면(예: 동전 단위 추가) 그리디 성질이 깨질 수 있으므로, 도메인 변경 시 재검증합니다.
요약하면, 코테 그리디는 “증명 가능한 구조를 빠르게 코드로 옮기는 훈련”이고, 프로덕션 그리디는 “증명 대신 관측과 가드레일로 리스크를 관리하는 휴리스틱”에 가깝습니다. 둘 다 “매 순간의 규칙”이라는 점에서는 연결됩니다.
심화 사례 (시스템·인프라)
공통점은 최적성 증명보다 SLO·비용·운영 리스크가 기준점이라는 것입니다.
- 적응형 스트리밍(ABR): 네트워크 상태에 따라 비트레이트를 단계적으로 오르내립니다. 전역 최적 재생 품질은 NP에 가까울 수 있지만, 버퍼·처리량 기반의 탐욕적 래더 전환이 실시간 시스템에서 널리 쓰입니다.
- CDN/엣지 캐시 축출: LRU/LFU 등은 “지금 가장 덜 중요해 보이는 항목을 버린다”는 휴리스틱이며, 실제로는 트래픽 패턴에 따라 Hit Rate가 달라집니다. 고정 그리디 ≠ 전역 최적임을 모니터링으로 상쇄합니다.
- 요청 합치기(배칭): 로그 전송·메트릭 flush에서 “큐가 차거나 시간 한도가 되면 한꺼번에 보낸다”는 배치 크기/지연 트레이드오프가 그리디에 가깝습니다.
- 쿠버네티스 스케줄링:
predicates(필터) 후priorities(점수)로 노드를 고르는 구조는 다목적 점수의 탐욕적 선택에 가깝습니다. 클러스터 전역 최적 배치는 별도 문제입니다. - 로드 밸런서: 라운드 로빈·최소 연결·가중 라운드 로빈 등은 지역 정보만 보고 다음 타깃을 고릅니다. 글로벌 최적 분배와는 다를 수 있으나 지연·구현 단순성을 얻습니다.
- 빈 패킹(Bin packing) 휴리스틱: First-Fit Decreasing 등은 근사로 쓰이며, 최적 빈 개수를 항상 주지는 않습니다.
운영 체크리스트 (추가)
- 카나리·점진 롤아웃: 그리디 정책을 바꿀 때는 트래픽 일부만 적용해 지표 회귀를 확인합니다.
- 최악 입력 시뮬레이션: 정렬 키가 동률일 때의 동작, 타이브레이커를 명시합니다.
- 이중 기준 구현: “코테 그리디”는 증명이 있을 때만, “프로덕션 그리디”는 가드레일·롤백이 있을 때만 채택합니다.
9. 실전 문제
문제 1: 체육복 (프로그래머스)
def solution(n, lost, reserve):
"""
체육복 빌려주기
"""
# 여벌 있는데 도난당한 학생 제외
lost_set = set(lost) - set(reserve)
reserve_set = set(reserve) - set(lost)
for r in sorted(reserve_set):
# 앞 번호 학생부터 빌려줌
if r - 1 in lost_set:
lost_set.remove(r - 1)
elif r + 1 in lost_set:
lost_set.remove(r + 1)
return n - len(lost_set)
# 테스트
print(solution(5, [2, 4], [1, 3, 5])) # 5문제 2: 조이스틱 (프로그래머스)
def solution(name):
"""
조이스틱 최소 이동 횟수
"""
answer = 0
min_move = len(name) - 1 # 오른쪽으로만 이동
for i, char in enumerate(name):
# 상하 이동 (A → char)
answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
# 좌우 이동 최적화
next_idx = i + 1
while next_idx < len(name) and name[next_idx] == 'A':
next_idx += 1
# 오른쪽 → 왼쪽 vs 왼쪽 → 오른쪽
min_move = min(
min_move,
i + i + len(name) - next_idx, # 오→왼
i + len(name) - next_idx + len(name) - next_idx # 왼→오
)
return answer + min_move
# 테스트
print(solution("JEROEN")) # 5610. 실전 팁
그리디 문제 판별법
다음 Python 예제 코드입니다.
# ✅ 그리디 신호
# 1. "최대/최소" + 정렬 힌트
# 2. 시간 제한 빡빡 (O(n log n) 필요)
# 3. 반례 찾기 어려움
# ❌ 그리디 불가능
# 1. 반례 존재
# 2. "모든 경우" 고려 필요
# 3. 이전 선택이 영향 (→ DP)11. 정리
핵심 요약
- 그리디: 매 순간 최선, 보통 정렬·우선순위 큐와 함께 (O(n \log n)) 전후
- 탐욕 선택 속성 + 최적 부분 구조: 최적성을 말하려면 둘을 어떻게 만족하는지 풀어 쓸 것
- 교환 논법: 임의 최적해를 탐욕 선택 쪽으로 바꿔도 목적 함수가 악화되지 않음을 보이는 대표 증명(회의실·분할 배낭·SJF 등)
- 매트로이드: 독립 집합 위 가중치 그리디가 최적인 잘 알려진 구조(크루스칼 등). 모든 그리디가 매트로이드는 아님
- 그리디 vs DP: 정렬 한 번에 불변식이 서면 그리디 후보, 반례·상태 의존이 강하면 DP·완탐으로 분기
- 실패 패턴: 0-1 배낭·임의 동전·집합 덮기 최적·일반 TSP 등은 지역 최선이 전역을 망가뜨리기 쉬움
- 프로덕션: 휴리스틱·측정·가드레일·카나리와 함께 쓰고, 도메인 변경 시 성질 재검증
추천 문제
백준:
프로그래머스:
관련 글
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「그리디 알고리즘 | 매 순간 최선 탐욕 알고리즘 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「그리디 알고리즘 | 매 순간 최선 탐욕 알고리즘 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 그리디 알고리즘의 정당성 증명과 반례 찾기, 활동 선택·배낭 문제·최소 신장 트리 등 필수 유형을 실전 예제로 정리. 교환 논법(Exchange Argument)부터 프로그래머스·백준 문제까지 단계별로 학습. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·배낭·스케줄링·증명 기법 [실전]
- C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]
- 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, 그리디, Greedy, 탐욕, 코딩테스트, 최적화 등으로 검색하시면 이 글이 도움이 됩니다.