#CS#Algorithm#Greedy
그리디 알고리즘: 당장 최선을 선택
마시멜로 실험 실패? 미래를 생각하지 않고 당장 눈앞의 이익만 쫓는 알고리즘. 하지만 때로는 그게 정답일 때가 있습니다.
2025년 4월 26일
Codemapo
마시멜로 실험 실패? 미래를 생각하지 않고 당장 눈앞의 이익만 쫓는 알고리즘. 하지만 때로는 그게 정답일 때가 있습니다.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.
미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?
이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?
매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.
유명한 심리학 실험이 있다. 아이 앞에 마시멜로 하나를 놓고 이렇게 말한다. "15분 기다리면 하나 더 줄게." 대부분의 아이는 참지 못하고 바로 먹어버린다. 나도 그랬을 것 같다.
그리디 알고리즘이 딱 그렇다. 지금 당장 눈앞에 보이는 최선을 선택한다. 나중에 어떤 결과가 올지, 더 나은 선택이 숨어있는지 신경 쓰지 않는다. 그냥 지금 여기서 가장 좋아 보이는 걸 집는다.
그런데 신기한 건, 이런 근시안적인 전략이 때로는 최적해를 준다는 사실이다. 스타트업 하면서 깨달은 건데, 세상 모든 문제가 "완벽한 계획"을 요구하진 않는다. 어떤 문제는 그냥 직감적으로 "지금 제일 좋은 거" 고르는 게 답이다.
내가 그리디를 처음 체감한 건 편의점 알바 시절이었다. 물건값 4,000원인데 손님이 만원을 냈다. 거스름돈 6,000원을 줘야 하는데, 당연히 동전/지폐 개수를 최소로 줘야 한다. 레지 서랍에는 5,000원권, 1,000원권, 500원, 100원이 있었다.
머리로 생각할 것도 없었다. 그냥 큰 단위부터 쓸 수 있는 만큼 쓴다.
끝. 총 2장. 이게 최소다.
이게 그리디다. "지금 쓸 수 있는 가장 큰 단위를 쓴다." 매 순간 탐욕적으로 최대를 선택한다. 그리고 이 경우엔 그게 정답이다.
서비스 운영하면서 배운 게 있다. "지금까지 잘 됐으니까 계속 될 거야"라는 가정은 위험하다는 것. 그리디도 마찬가지다.
동전 단위가 100원, 400원, 500원이고, 800원을 거슬러줘야 한다고 가정하자.
그리디 방식:총 4개.
그런데 잠깐. 400원짜리 2개면 800원이다. 2개면 끝이었다. 그리디는 500원을 덥썩 물어버려서 더 나쁜 해를 만들었다.
이게 그리디의 딜레마다. 눈앞의 "최대 단위"라는 미끼에 물려서 전체 최적해를 놓친다. 이럴 땐 동적 프로그래밍(DP)처럼 모든 경우를 따져봐야 한다.
프로젝트에서 자주 묻는 질문이 있다. "이거 그리디로 풀 수 있어요?" 내 대답은 항상 똑같다. "두 가지 조건이 만족되면 됩니다."
지금 최선의 선택이 나중에 문제를 일으키지 않는다는 보장. 앞에서 큰 단위 동전을 쓴다고 해서 뒤의 선택지가 망가지지 않는다면, 그리디가 통한다.
거스름돈 문제에서 5000, 1000, 500, 100은 큰 단위가 작은 단위의 배수 관계에 있다. 그래서 큰 거 먼저 쓰는 게 항상 유리하다. 하지만 100, 400, 500은 배수 관계가 아니라서 그리디가 실패한다.
전체 문제의 최적해가 부분 문제의 최적해로 구성된다는 속성. 6,000원 거스름돈 최적해 = 5,000원 쓰고 남은 1,000원의 최적해. 이렇게 재귀적으로 쪼갤 수 있다면 그리디가 먹힌다.
DP와 다른 점은, DP는 "모든 부분 문제를 다 본다"는 거고, 그리디는 "지금 최선만 본다"는 것이다. 그리디가 훨씬 빠르지만 조건이 까다롭다.
일반적인 화폐 단위에서 작동하는 그리디 거스름돈 코드.
function makeChange(amount, denominations) {
// 큰 단위부터 정렬
const sorted = [...denominations].sort((a, b) => b - a);
const result = [];
let remaining = amount;
for (const coin of sorted) {
while (remaining >= coin) {
result.push(coin);
remaining -= coin;
}
}
return remaining === 0 ? result : null; // 거슬러줄 수 없으면 null
}
console.log(makeChange(6000, [5000, 1000, 500, 100]));
// [5000, 1000] → 2개
console.log(makeChange(800, [500, 400, 100]));
// [500, 100, 100, 100] → 4개 (최적해는 400+400=2개인데 그리디는 실패)
시간 복잡도: O(n log n) (정렬) + O(amount / min_coin) (루프) 공간 복잡도: O(result size)
이 코드는 "큰 것부터 쓴다"는 그리디 전략을 충실히 따른다. 하지만 화폐 단위에 따라 최적해를 보장하지 못한다.
스타트업 사무실에 회의실이 하나밖에 없다고 치자. 여러 팀이 시간대를 신청했는데, 겹치는 회의는 동시에 할 수 없다. 최대한 많은 회의를 배정하려면?
| 회의 | 시작 | 종료 |
|---|---|---|
| A | 9:00 | 10:30 |
| B | 9:30 | 11:00 |
| C | 10:00 | 11:30 |
| D | 10:30 | 12:00 |
| E | 11:00 | 12:30 |
직관: "빨리 끝나는 회의부터 배정한다." 일찍 끝날수록 다음 회의를 받을 여유가 많기 때문이다.
function activitySelection(activities) {
// 종료 시간 기준 오름차순 정렬
const sorted = [...activities].sort((a, b) => a.end - b.end);
const selected = [];
let lastEndTime = 0;
for (const activity of sorted) {
// 이전 회의 끝난 후에 시작하는 회의만 선택
if (activity.start >= lastEndTime) {
selected.push(activity);
lastEndTime = activity.end;
}
}
return selected;
}
const meetings = [
{ name: 'A', start: 9, end: 10.5 },
{ name: 'B', start: 9.5, end: 11 },
{ name: 'C', start: 10, end: 11.5 },
{ name: 'D', start: 10.5, end: 12 },
{ name: 'E', start: 11, end: 12.5 }
];
console.log(activitySelection(meetings));
// [A, D, E] → 3개 회의 배정
왜 이게 최적인가? 종료 시간이 빠르면 뒤에 선택지가 많아진다. 탐욕적으로 "빨리 끝나는 것"을 선택해도 전체 최적해를 놓치지 않는다. 이게 그리디의 마법이다.
시간 복잡도: O(n log n) (정렬) 공간 복잡도: O(n) (결과 배열)
배낭에 물건을 담는데, 무게 제한이 있다. 가치를 최대화하려면?
Fractional Knapsack: 물건을 쪼갤 수 있다. (예: 금가루) 0/1 Knapsack: 물건을 통째로만 담을 수 있다. (예: 노트북)
Fractional은 그리디가 통한다. 단위 무게당 가치(value/weight)가 높은 것부터 담으면 된다. 마치 주식을 살 때 "수익률 높은 것부터" 사는 것과 같다.
0/1은 그리디가 실패한다. DP를 써야 한다. 왜냐하면 "지금 가치 높은 물건"을 담았다가 무게가 남아서 더 나쁜 조합이 될 수 있기 때문이다.
파일 압축에 쓰인다. 자주 나오는 문자는 짧은 비트로, 덜 나오는 문자는 긴 비트로 인코딩한다. 빈도가 가장 낮은 두 노드를 합친다는 그리디 전략으로 최적 압축 트리를 만든다.
마치 택배 박스 포장할 때, 자주 쓰는 물건은 가까운 곳에 두고, 안 쓰는 건 깊숙이 넣는 것과 같다.
그래프의 모든 정점을 연결하되, 총 간선 가중치를 최소화한다. 그리디 전략: 가중치가 가장 작은 간선부터 추가하되, 사이클이 생기면 건너뛴다.
회사 각 지사를 연결하는데 전선 비용을 최소화하는 것과 같다. 일단 가장 싼 연결부터 하되, 이미 연결된 곳끼리는 또 연결하지 않는다.
출발점에서 각 정점까지 최단 거리를 구한다. 그리디 전략: 현재까지 알려진 거리가 가장 짧은 정점을 방문한다.
네비게이션이 "지금까지 가장 가까운 교차로"부터 탐색하는 것과 같다. 일단 가까운 데부터 확정 짓고 나간다.
서버에서 여러 작업을 처리해야 하는데, 대기 시간을 최소화하려면? 실행 시간이 짧은 작업부터 처리한다. (SJF, Shortest Job First)
카페에서 "아이스 아메리카노"는 10초, "핸드드립"은 5분 걸린다면, 아메리카노 주문 10개를 먼저 처리하는 게 전체 대기 시간을 줄인다.
그리디 알고리즘이 정말 최적해인지 증명하는 기법이다. "최적해가 그리디 해와 다르다고 가정 → 최적해를 그리디 해로 바꿔도 더 나빠지지 않음 → 모순" 이렇게 증명한다.
회의실 배정 예시:
이런 식으로 "교환해도 안 나빠진다"를 보이는 게 Exchange Argument다.
세 가지를 비교하면 이렇다.
| 전략 | 특징 | 예시 |
|---|---|---|
| Greedy | 지금 최선만 선택, 뒤 안 돌아봄 | 거스름돈, 활동 선택, MST |
| DP | 모든 부분 문제 풀고 조합 | 0/1 배낭, 최장 공통 부분 수열 |
| Backtracking | 모든 경우 탐색하되 가지치기 | N-Queens, 스도쿠 |
속도: Greedy > DP > Backtracking 최적해 보장: 조건부(Greedy) < 보장(DP, Backtracking)
그리디는 가장 빠르지만, 문제가 그리디 조건을 만족해야 한다. DP는 느리지만 확실하다. Backtracking은 완전 탐색이라 더 느리지만 제약 조건이 복잡할 때 쓴다.
클라우드 서비스를 운영하면서 겪은 일이다. 서버 대역폭이 제한적인데, 여러 API 요청이 들어온다. 각 요청마다 "처리 시간"과 "중요도"가 다르다.
초기엔 "중요도 높은 것부터"라는 그리디 전략을 썼다. 그런데 중요한 요청이 오래 걸리면, 뒤에 쌓인 짧은 요청들이 대기 시간 폭발했다.
결국 SJF(Shortest Job First) + Priority Queue를 섞었다. 짧은 것 우선이되, 일정 중요도 이상은 우선 처리. 이것도 일종의 "그리디 휴리스틱"이다. 완벽한 최적해는 아니지만, 실시간으로 빠르게 결정해야 할 때 그리디 전략은 유용했다.
그리디는 "마시멜로 실험 실패"처럼 보인다. 눈앞의 것만 보고, 미래를 생각 안 한다. 하지만 문제 구조가 그리디를 허용한다면, 이게 가장 빠르고 우아한 해법이다.
회사 운영도 그렇다. 모든 결정을 완벽하게 계획할 순 없다. 때로는 "지금 당장 최선"을 선택하고 빠르게 나가는 게 답이다. 다만, 그게 통하는 문제인지, 아니면 신중하게 모든 경우를 따져봐야 하는 문제인지 구분하는 눈이 필요하다.
그리디 알고리즘은 "언제 욕심을 부려도 되는지"를 가르쳐준다. Greedy Choice Property와 Optimal Substructure, 이 두 조건이 만족되면 망설이지 말고 큰 것부터 집어라. 거스름돈도, 회의실도, 네트워크 경로도.
다음에 "지금 당장 제일 좋은 거 고르면 되지 않나?"라는 생각이 들 때, 그게 그리디가 통하는 문제인지 한 번 체크하자. 동전 단위가 배수 관계인지, 빨리 끝나는 게 진짜 유리한지. 그게 맞다면, 그냥 덥썩 물어라.