그리디 알고리즘

수치해석 최적설계 마지막 수정: 2026-08-31 04:51:37

1. 개요[편집]

그리디 알고리즘 Greedy algorithm
전략	매 단계 국소 최적을 고르고 되돌리지 않는다
정당성 도구	교환 논증 · 매트로이드(라도-에드먼즈 정리)
필요 성질	탐욕 선택 성질 + 최적 부분구조
최적인 예	MST · 허프만 부호 · 구간 스케줄링 · 분수 배낭
실패하는 예	0-1 배낭 — 근사비 하한이 없다
보장이 붙는 예	집합 커버 $\ln n$ · 단조 부분모듈 최대화 $1-1/e$
실무 위치	메시·색칠·순서화의 사실상 기본값

지금 제일 좋아 보이는 걸 집는다. 그리고 후회하지 않는다.

그리디 알고리즘(greedy algorithm, 탐욕 알고리즘)은 매 단계에서 그 순간 가장 좋아 보이는 선택을 하고 이후에 그 선택을 절대 되돌리지 않는 알고리즘 설계 패러다임이다. 미래를 보지 않고, 대안을 저장하지 않으며, 되돌아가지 않는다. 그래서 대개 정렬 한 번 + 선형 스캔, 또는 우선순위 큐 한 개로 끝나고 비용은 $O(n\log n)$ 언저리에 머문다.

문제는 이렇게 무모한 전략이 왜 가끔 정말로 최적해를 주느냐다. 동적 계획법은 모든 부분문제를 다 풀어서, 분할 정복은 부분해를 제대로 결합해서, 백트래킹은 안 되는 경우를 다 배제해서 정답을 얻는다. 그리디는 그중 아무것도 하지 않는다. 그런데도 최소 신장 트리나 허프만 부호에서는 최적이 증명된다. 이 문서의 절반은 그 증명이 왜 되는지, 나머지 절반은 안 될 때 어떻게 되는지에 대한 것이다.

그리고 시뮬레이션 실무 관점에서 중요한 사실 하나. 최적성이 증명되지 않는 자리에서도 그리디는 압도적으로 자주 쓰인다. 메시 단순화, 희소행렬 순서화, 그래프 색칠, BVH 구축 — 이들의 산업 표준은 거의 전부 그리디 휴리스틱이다. 정확해가 NP-난해라서 어쩔 수 없기도 하지만, 근본적으로는 실측 품질 대비 비용이 압도적이기 때문이다.

2. 최적이 되기 위한 두 조건[편집]

그리디가 최적해를 주려면 두 가지가 필요하다.

탐욕 선택 성질(greedy-choice property). 국소 최적 선택 하나를 포함하는 전역 최적해가 적어도 하나 존재한다. “모든 최적해가 그 선택을 포함한다”가 아니라 “하나는 포함한다”로 충분하다는 점이 중요하다.

최적 부분구조(optimal substructure). 그 선택을 확정한 뒤 남는 문제도 같은 종류의 문제이고, 그 부분문제의 최적해와 방금의 선택을 합치면 원 문제의 최적해가 된다.

두 번째는 동적 계획법과 공유하는 성질이고, 그리디를 그리디로 만드는 것은 첫 번째다. 동적 계획법은 여러 선택지를 다 시도해 보고 나중에 최선을 고르지만, 탐욕 선택 성질이 있으면 시도할 필요 자체가 없다.

이 성질을 실제로 증명하는 표준 도구가 두 가지 있는데, 하나는 문제별 수작업이고 다른 하나는 구조 이론이다.

3. 도구 1 — 교환 논증[편집]

교환 논증(exchange argument)은 이렇게 간다. 최적해 $O$ 를 아무거나 하나 가져와서, 그리디의 선택 $g$ 를 포함하지 않는다고 하자. $O$ 에서 뭔가를 빼고 $g$ 를 넣어도 여전히 실행가능하고 목적함수가 나빠지지 않는다는 것을 보인다. 그러면 $g$ 를 포함하는 최적해가 존재한다. 이걸 단계마다 반복(귀납)하면 그리디의 출력 전체가 최적해가 된다.

최소 신장 트리의 컷 속성이 정확히 이 논증이다 — 컷을 가로지르는 최소 간선 $e$ 를 안 쓴 신장 트리에 $e$ 를 넣으면 사이클이 생기고, 그 사이클이 컷을 다시 가로지르는 간선 $f$ 를 빼면 가중치가 늘지 않는다.

허프만 부호화의 정당성도 교환 논증이다. 빈도가 가장 낮은 두 심벌 $x,y$ 를 보자. 최적 접두 부호의 이진 트리에서 깊이가 최대인 두 잎은 반드시 형제이고(아니면 부모를 잎으로 바꿔 비용을 줄일 수 있다), 그 형제 자리에 $x,y$ 를 놓아도 비용이 늘지 않는다(빈도가 낮은 것을 깊은 곳에 두는 것이 항상 유리하므로 교환해도 손해가 없다). 따라서 $x,y$ 를 형제로 만드는 최적해가 존재하고, 둘을 합친 가상 심벌로 알파벳을 하나 줄여 귀납하면 끝난다. 허프만(D. A. Huffman, 1952)이 학기 과제로 이걸 풀어 냈다는 일화는 유명하다.¹ 결과 부호의 평균 길이는 엔트로피 $H$ 와 $H+1$ 사이에 갇히고, 이 한 알고리즘이 이미지 압축과 무손실 압축 포맷 대부분의 마지막 단계에 들어앉아 있다.

구간 스케줄링은 “그리디가 앞서 나간다”(greedy stays ahead) 형태의 변종이다. 서로 겹치지 않는 구간을 최대 개수로 고르는 문제에서 끝나는 시각이 가장 이른 것부터 고르면 최적이다. 귀납으로, 그리디가 $k$ 개를 골랐을 때 그 $k$ 번째 구간의 종료 시각은 어떤 최적해의 $k$ 번째보다 늦지 않다. 자원을 더 빨리 비워 주니 뒤에 남는 선택지가 최소한 같거나 많다는 것. 참고로 시작 시각이 이른 것부터나 길이가 짧은 것부터는 전부 반례가 있다. 그리디에서 “무엇을 기준으로 탐욕할 것인가”는 알고리즘 전체를 좌우하는 설계 결정이지 사소한 디테일이 아니다.

4. 도구 2 — 매트로이드[편집]

교환 논증은 문제마다 새로 짜야 한다. 매트로이드(matroid)는 “그리디가 통하는 구조”를 한 번에 특징짓는다. 유한 집합 $E$ 와 부분집합족 $\mathcal{I}$ 의 쌍 $(E,\mathcal{I})$ 가 매트로이드라는 것은,

$\emptyset \in \mathcal{I}$ ,
유전성 — $B\in\mathcal{I}$ 이고 $A\subseteq B$ 면 $A\in\mathcal{I}$ ,
교환 공리 — $A,B\in\mathcal{I}$ , $|A|<|B|$ 면 어떤 $x\in B\setminus A$ 가 있어 $A\cup\{x\}\in\mathcal{I}$

를 만족한다는 뜻이다. $\mathcal{I}$ 의 원소를 독립집합이라 부른다. 벡터공간의 일차독립 집합족이 대표 예이고, 그래프에서 사이클 없는 간선 집합족(그래픽 매트로이드)이 우리가 쓰는 예다.

라도-에드먼즈 정리. 유전적 집합족 $(E,\mathcal{I})$ 에 대해, 모든 가중치 함수 $w: E \to \mathbb{R}_{\ge 0}$ 에서 그리디(가중치 큰 것부터 독립성을 깨지 않으면 넣기)가 최대 가중치 독립집합을 주는 것은 $(E,\mathcal{I})$ 가 매트로이드인 것과 동치다.

“동치”라는 점이 핵심이다. 매트로이드면 그리디가 되는 것뿐 아니라, 그리디가 항상 되면 그건 매트로이드다. 크러스컬 알고리즘이 그래픽 매트로이드의 그리디라는 사실은 이 정리의 한 줄 따름정리이고, 반대로 어떤 문제에서 그리디가 실패하는 반례를 하나라도 찾았다면 그 문제의 실행가능 구조는 매트로이드가 아니라는 것이 증명된 것이다.

경계도 분명하다. 매트로이드 두 개의 공통 독립집합을 최대화하는 문제(매트로이드 교집합)는 다항 시간에 풀리지만 그리디로는 안 되고, 세 개부터는 NP-난해다. 그리디의 유효 범위가 생각보다 좁다는 것을 이 계단이 잘 보여준다. 순서가 의미를 갖는 문제로 확장한 그리도이드(greedoid) 같은 일반화도 있지만, 실무에서 “이건 매트로이드인가?”를 진지하게 따지는 경우는 드물고 대개 교환 논증으로 때린다.

5. 실패할 때 — 0-1 배낭[편집]

그리디가 처참하게 지는 표준 예가 **0-1 배낭 문제**다. 용량 $W$ , 물건 $i$ 는 무게 $w_i$ ·가치 $v_i$ , 쪼갤 수 없다. 그럴듯한 기준은 단위 무게당 가치 $v_i/w_i$ 내림차순인데,

용량 $W=M$ , 물건 A는 $w=1, v=2$ , 물건 B는 $w=M, v=M$ .
비율은 A가 2, B가 1이라 그리디는 A를 먼저 넣고 남은 용량 $M-1$ 로 B를 못 넣어 끝난다. 총 가치 2.
최적은 B 하나로 $M$ .

$M$ 을 키우면 비율이 무한히 나빠진다. 즉 0-1 배낭에 대한 비율 그리디는 근사비 자체가 존재하지 않는다. ( $\max$ (그리디 해, 가장 비싼 물건 하나)로 고치면 그제서야 2-근사가 된다.)

반면 쪼갤 수 있는 분수 배낭에서는 같은 그리디가 최적이다. 이 차이가 그리디의 성격을 정확히 드러낸다 — 되돌리기가 없다는 제약은 실행가능 영역이 연속적으로 이어져 있을 때는 문제가 안 되지만, 정수 제약이 구멍을 뚫어 놓으면 한 번의 잘못된 커밋을 만회할 길이 없다. 0-1 배낭의 정답은 동적 계획법이거나 분지한정법이고, 이 문제가 정수계획법 교과서의 첫 페이지에 있는 이유이기도 하다.

6. 최적이 아니어도 보장이 붙을 때[편집]

최적이 아니라도 얼마나 나쁠 수 있는지 상한이 증명되면 그리디는 충분히 훌륭한 답이다. 대표적인 두 가지.

집합 커버 — $\ln n$ . 남은 원소를 가장 많이 덮는 집합을 매번 고르는 그리디는 $H_n \le \ln n + 1$ 근사이고, 이 상수는 개선 불가임이 알려져 있다. 자세한 것은 근사 알고리즘 문서에 있다.

단조 부분모듈 최대화 — $1-1/e$ . 집합함수 $f$ 가 부분모듈(submodular)이라는 것은 수확 체감을 뜻한다. $A \subseteq B$ 이고 $x \notin B$ 일 때

f(A\cup\{x\}) - f(A) \;\ge\; f(B\cup\{x\}) - f(B).

여기에 단조성( $A\subseteq B \Rightarrow f(A)\le f(B)$ )과 $f(\emptyset)=0$ 을 더하고, 크기 제약 $|S|\le k$ 아래 $f$ 를 최대화하는 문제를 생각하자. 한계 이득이 가장 큰 원소를 매번 하나씩 고르는 그리디는

f(S_{\text{greedy}}) \;\ge\; \left(1 - \frac{1}{e}\right) f(S^{*}) \approx 0.632\, f(S^{*})

를 보장한다(Nemhauser–Wolsey–Fisher, 1978). 게다가 이 상수는 값 오라클 모형에서 개선 불가이고, $P \ne NP$ 아래서도 개선 불가다. 시뮬레이션 실무에서 이게 반가운 이유는 센서·측정점 배치가 정확히 이 형태이기 때문이다. 가우스 과정 모형에서 관측 집합의 상호정보량·엔트로피 감소는 (조건에 따라) 부분모듈이므로, “센서 $k$ 개를 어디에 둘 것인가”를 그리디로 풀면 63% 보장이 딸려 온다. 실험 설계, 축소 기저 모형의 스냅숏 선택, 적응 격자의 세분화 지표 선택에도 같은 논리가 쓰인다.

7. 시뮬레이션 실무에서 그리디가 국룰인 자리[편집]

그래프 색칠. 희소 야코비안의 열 압축, 병렬 스무더의 적흑/다색 순서화는 전부 그래프 색칠이고, 실무 해법은 예외 없이 탐욕 채색이다. 순서를 매 단계 다시 고르는 DSATUR 이 사실상 표준. 자세한 것은 해당 문서에 있다.
희소행렬 순서화. LU·촐레스키의 채움현상을 줄이는 최소 차수(minimum degree) 계열과 가우스 소거법의 마코위츠 피벗팅은 “이번 단계에서 채움이 가장 적어 보이는 축을 고른다”는 순수 그리디다. 전역 최적 순서화는 NP-난해이므로 애초에 다른 선택지가 없다. 대안인 중첩 절단은 분할 정복 쪽 사고이고, 현대 솔버는 둘을 섞어 쓴다.
메시 생성과 단순화. 전진 전면법은 매 단계 가장 짧은 전면 간선을 골라 요소를 붙인다. 들로네 세분화는 가장 나쁜 요소를 골라 외심을 삽입한다. 메시 감량(decimation)은 오차 증가가 가장 작은 모서리 축약을 우선순위 큐에서 뽑는다 — 이차 오차 계량(QEM) 방식이 그것이다. 셋 다 되돌리기가 없고, 셋 다 전역 최적이라는 보장이 없으며, 셋 다 산업 표준이다.
경계 볼륨 계층 구축. 표면적 휴리스틱으로 분할 위치를 고르는 하향식 BVH 빌드는 각 노드에서 국소 비용만 보고 자르는 그리디다. 전역 최적 BVH 는 구할 수 없고, 그리디 SAH 트리가 레이 트레이싱 성능의 기준선이 된 지 오래다.
라벨 설정 최단경로. 다익스트라 알고리즘과 고속 행진법은 “가장 작은 잠정 값을 가진 노드를 확정한다”는 그리디이고, 여기서는 최적성이 증명된다(비음 가중치·단조 전파라는 조건 덕분에). 같은 그리디라도 구조가 받쳐 주면 근사가 아니라 정확해가 된다는 좋은 대비.
거친 격자와 분할. 다중격자법의 대수적 조대화, 그래프 분할의 다단계 알고리즘에서 쓰는 무거운 간선 매칭(heavy-edge matching)은 간선을 가중치 순으로 훑으며 양 끝이 아직 안 묶였으면 묶는 그리디 매칭이다. 최대 가중치 매칭의 절반은 보장된다.
패킹. 텍스처 아틀라스, 라이트맵 배치, 작업 스케줄링에 쓰는 first-fit decreasing 은 그리디 상자 채우기이고, 최적 상자 수 대비 $\tfrac{11}{9}\mathrm{OPT} + \tfrac{6}{9}$ 라는 타이트한 한계가 알려져 있다.

정리하면, 그리디가 실무를 장악한 이유는 최적이어서가 아니다. 비용이 낮고, 구현이 짧고, 품질이 대체로 최적의 몇 % 안에 들어오며, 대안이 지수 시간이기 때문이다. 다만 그 대가로 “왜 이 메시가 여기서 이렇게 잘렸지” 같은 질문에 답하기 어려워진다 — 그리디의 결과는 입력 순서와 타이브레이크에 민감해서, 같은 코드가 부동소수점 반올림 하나로 다른 답을 내기도 한다.² 재현성이 필요하면 정렬 키에 결정적 타이브레이크를 반드시 박아 넣어야 한다.³

8. 관련 문서[편집]

지도교수 파노가 “기말 시험을 볼래, 최적 부호 문제를 풀래”라고 했고, 허프만은 후자를 골랐다가 몇 달을 헤맸다고 한다. 포기하고 노트를 버리려던 순간 아이디어가 떠올랐다는 것이 본인 회고다. 참고로 그 파노가 이미 만들어 둔 섀넌-파노 부호는 하향식이라 최적이 아니었고, 허프만의 상향식이 최적이었다. 시험 대신 논문을 쓴 학생의 승리. ↩
특히 메시 코드에서 악명 높다. 같은 소스, 같은 입력, 다른 컴파일러 최적화 플래그에서 요소 수가 몇 개 달라지는 현상의 범인은 대개 그리디 선택의 타이브레이크가 부동소수점 비교에 걸려 있는 것이다. 물리가 바뀐 게 아니라 정렬이 바뀐 것이다. ↩
절대 하지 말아야 할 것: 타이브레이크를 포인터 주소나 해시 순회 순서로 두는 것. 실행할 때마다 답이 바뀌고, 그 사실을 알아채는 데 3개월이 걸린다. ↩