욕심쟁이 알고리즘(Greedy algorithm)

욕심쟁이 알고리즘은 답을 한 조각씩 쌓아 가면서, 매번 지금 당장 가장 좋아 보이는 조각을 고르고 다시는 되돌아보지 않습니다. 멀리 내다보지 않으니 빠르고 간단합니다. 문제는 그렇게 모은 답이 정말 가장 좋은 답이냐는 것인데, 문제에 따라 늘 그렇기도 하고 크게 틀리기도 합니다.

거스름돈이 전형적인 예입니다. 남은 금액을 넘지 않는 가장 큰 동전부터 냅니다. 동전 로 원을 거슬러 줘 봅시다.

1, 5, 10, 50처럼 우리가 쓰는 동전 체계에서는 욕심쟁이가 늘 가장 적은 개수를 냅니다. 그러나 1, 3, 4원짜리만 있으면 6원을 4 + 1 + 1로 세 개 내는데, 3 + 3 두 개면 충분합니다. 큰 동전을 먼저 쓴 선택이 나중의 가능성을 막아 버린 것입니다. 이럴 때는 1원부터 차례로 모든 금액의 최소 개수를 표에 채우는 동적 계획법⁠(dynamic programming)⁠으로 정확한 답을 구합니다. 아래 줄이 그렇게 구한 답입니다.

욕심쟁이가 옳다는 것은 보통 바꿔치기로 증명합니다. 가장 좋은 답이 욕심쟁이의 첫 선택과 다르다면, 그 부분을 욕심쟁이의 선택으로 바꿔도 나빠지지 않음을 보이는 것입니다. 이렇게 증명되는 대표적인 예가 순환을 만들지 않는 한 가장 짧은 변부터 고르는 크러스컬의 최소 신장 트리, 가장 드문 두 기호부터 묶는 허프만 부호⁠(Huffman coding)⁠, 가장 가까운 점부터 확정하는 다익스트라 알고리즘(에츠허르 데이크스트라)의 최단 경로⁠(shortest path)⁠입니다. 다익스트라 알고리즘⁠(Dijkstra's algorithm)⁠은 변의 길이가 음수가 아닐 때만 옳습니다. 음수 변이 있으면 이미 확정한 점에 나중에 더 짧은 길이 생길 수 있기 때문입니다. 회의실 하나에 겹치지 않게 가장 많은 회의를 넣는 문제에서도 '가장 일찍 끝나는 회의부터'라는 욕심이 정답을 줍니다.

반면 여러 도시를 한 번씩 도는 가장 짧은 길을 '가장 가까운 도시부터' 고르는 방법은 최적보다 훨씬 긴 길을 내기도 하고, 나라마다 차례로 이웃과 겹치지 않는 가장 앞 번호의 색을 칠하는 방법은 순서에 따라 4색 정리⁠(four color theorem)⁠가 보장하는 네 가지보다 많은 색을 쓰기도 합니다. 이런 실패는 언덕을 오를 때 늘 가장 가파른 쪽으로만 가다가 가까운 봉우리(국소 최적)에 갇히는 것과 닮았습니다. 연속적인 최적화⁠(optimization)⁠에서 경사 하강법⁠(gradient descent)⁠이 빠지는 함정도 같은 모양입니다.

이어지는 곳. 1, b, b², …처럼 진법⁠(positional notation)⁠의 자릿값으로 된 동전이라면 욕심쟁이가 언제나 최적이고, 그 답은 금액을 b진법으로 쓴 각 자리의 숫자입니다. 수에서 정수⁠(integer)⁠ 부분을 최대한 떼어 내고 나머지를 뒤집기를 되풀이하는 연분수⁠(continued fraction)⁠ 전개도 욕심쟁이 과정입니다. 욕심쟁이가 언제 옳은지는 매트로이드⁠(matroid)⁠라는 구조로 깔끔하게 설명됩니다. 매트로이드는 '독립⁠(independence)⁠'이라 부르는 부분집합⁠(subset)⁠들의 모임으로, 독립인 집합⁠(set)⁠의 부분집합은 여전히 독립이고, 작은 독립 집합은 더 큰 독립 집합에서 원소⁠(element)⁠ 하나를 빌려 와 독립을 유지한 채 늘릴 수 있다는 두 규칙을 지킵니다. 원소마다 양수 무게가 있을 때 무게의 합이 가장 큰 독립 집합을 찾는 문제는, 이 두 규칙이 성립하면 욕심쟁이(무거운 것부터, 독립이 깨지지 않는 한 담기)가 언제나 정확히 풉니다. 거꾸로, 첫째 규칙을 지키는 모임에서 어떤 무게를 주어도 욕심쟁이가 통한다면 그 모임은 둘째 규칙도 지킵니다. 그래프에서 순환을 만들지 않는 변들의 모임이 대표적인 매트로이드이고, 그래서 최소 신장 트리에서 욕심쟁이가 통합니다. 언어 모델⁠(language model)⁠이 매번 확률⁠(probability)⁠이 가장 큰 토큰⁠(token)⁠ 하나를 고르는 탐욕 디코딩⁠(greedy decoding)⁠도 욕심쟁이라서, 확률이 가장 큰 문장을 찾는다는 보장이 없습니다(디코딩).