그리디 알고리즘

그리디 알고리즘은 매번 지금 가장 좋아 보이는 것을 고릅니다. 그렇게 답을 한 조각씩 쌓습니다. 거스름돈을 큰 동전부터 채우는 것이 그 예입니다. 한 번 고른 것은 되돌리지 않습니다. 그래서 선택지를 모두 따져 보지 않고 후보를 한 번 훑어 끝냅니다. 프림 알고리즘과 다익스트라 알고리즘도 이 방식으로 가장 좋은 답을 내는 알고리즘입니다.

상세

그리디 알고리즘(greedy algorithm)은 알고리즘을 짜는 한 가지 방식입니다. 문제 하나를 푸는 특정한 절차가 아닙니다. 여러 알고리즘이 함께 쓰는 뼈대입니다. 「그리디」는 욕심을 부린다는 뜻의 영어 낱말이라 탐욕 알고리즘이라고도 부릅니다.

고르고 되돌리지 않는 뼈대

그리디 알고리즘은 답을 한 번에 만들지 않습니다. 후보를 하나씩 봅니다. 그리고 답에 넣을지 말지를 정합니다. 매번 볼 후보는 정해 둔 기준으로 지금 가장 좋아 보이는 것입니다.

한 번 넣은 후보는 끝까지 빼지 않습니다. 나중에 더 나은 조합이 보여도 앞의 선택을 고치지 않습니다. 후보마다 한 번만 판단하므로 계산이 적게 듭니다.

가능한 조합을 전부 만들어 보고 가장 좋은 것을 고르는 방법을 완전 탐색이라고 합니다. 완전 탐색은 가장 좋은 답을 늘 찾습니다. 대신 후보가 하나 늘 때마다 따질 조합 수가 두 배가 됩니다. 그리디 알고리즘은 그 조합들을 따지지 않고 한 갈래만 따라갑니다.

넣어도 되는지를 가르는 규칙은 문제마다 다릅니다. 거스름돈에서는 남은 금액을 넘지 않아야 합니다. 회의실 배정에서는 이미 넣은 회의와 시간이 겹치지 않아야 합니다. 후보를 한 번 판단하는 흐름을 그리면 아래와 같습니다.

flowchart TD
    A["후보를 기준에 맞춰 늘어놓는다"] --> B["맨 앞 후보를 꺼낸다"]
    B --> C{"넣어도 규칙을 안 어기나"}
    C -->|예| D["답에 넣는다 · 다시 빼지 않는다"]
    C -->|아니오| E["버린다"]
    D --> F{"후보가 남았나"}
    E --> F
    F -->|예| B
    F -->|아니오| G["모은 것이 답이다"]

거스름돈으로 본 뼈대

거스름돈을 가장 적은 동전으로 주는 문제를 거스름돈 문제라고 합니다. 그리디 알고리즘은 이 문제를 큰 동전부터 채우는 방식으로 풉니다. 아래 코드는 한국 동전 네 가지로 660원을 만듭니다.

def change(amount, coins):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used

won = [10, 50, 100, 500]
change(660, won)   # [500, 100, 50, 10]
change(160, won)   # [100, 50, 10]

sorted(..., reverse=True) 가 후보인 동전을 큰 것부터 늘어놓습니다. while 은 그 동전을 남은 금액을 넘지 않는 만큼 넣습니다. 더 넣을 수 없으면 그 동전은 버리고 다음 동전으로 넘어갑니다.

660원에서 500원을 넣으면 160원이 남습니다. 160원에는 500원이 안 들어가므로 500원은 버립니다. 이렇게 동전 4개로 끝납니다. 이것이 가장 적은 개수입니다.

가장 좋은 답을 놓치는 경우

같은 코드에 동전 종류만 바꿔 넣어 봅니다. 동전이 1원·3원·4원이고 6원을 만듭니다.

change(6, [1, 3, 4])   # [4, 1, 1]

그리디 알고리즘은 가장 큰 4원을 먼저 넣습니다. 남은 2원은 1원 둘로 채워 동전이 3개 듭니다. 3원 두 개를 쓰면 2개로 끝나므로 이 답은 틀렸습니다.

첫 선택이 갈림길입니다. 아래 그림에서 「그리디가 고름」이라고 적힌 길이 그리디 알고리즘이 가는 길입니다. 3원으로 시작하는 길이 가장 적은 개수로 가는 길입니다. 4원을 넣는 순간 3원으로 시작하는 길은 닫힙니다. 한 번 넣은 동전을 빼지 않으므로 다시 열리지도 않습니다.

flowchart TD
    S["6원"] -->|"그리디가 고름 · 4원"| A["남은 2원"]
    A -->|1원| B["남은 1원"]
    B -->|1원| C["0원 · 동전 3개"]
    S -->|3원| D["남은 3원"]
    D -->|3원| E["0원 · 동전 2개"]

알고리즘은 이 답이 틀렸다는 것을 스스로 알지 못합니다. 코드는 멀쩡히 끝납니다. 목록도 돌려줍니다. 그래서 그리디 알고리즘을 쓰려면 그 문제에서 이 방식이 통한다는 것을 먼저 따져 봐야 합니다.

탐욕 선택 속성과 최적 부분 구조

이 소절은 그리디 알고리즘이 통하는 문제를 두 성질로 가립니다. 문제가 두 성질을 다 갖추면 그리디 알고리즘이 가장 좋은 답을 냅니다. 가장 좋은 답을 최적해라고 부릅니다.

첫째 성질은 탐욕 선택 속성(greedy choice property)입니다. 지금 가장 좋아 보이는 선택을 포함하는 최적해가 적어도 하나 있다는 성질입니다. 이 성질이 있어야 첫 선택을 해도 최적해로 가는 길이 닫히지 않습니다.

1원·3원·4원 동전으로 6원을 만드는 문제에는 이 성질이 없습니다. 6원의 최적해는 3원 두 개뿐입니다. 4원을 넣은 최적해가 하나도 없으므로 4원을 고르는 순간 최적해를 잃습니다.

한국 동전은 큰 동전이 작은 동전의 배수로 짜여 있습니다. 10원 다섯 개로 50원을 채운 묶음은 50원 하나로 바꾸면 개수가 줄어듭니다. 그래서 큰 동전을 넣을 수 있을 때 큰 동전을 쓰는 최적해가 늘 있습니다.

둘째 성질은 최적 부분 구조(optimal substructure)입니다. 선택 하나를 한 뒤 남은 작은 문제의 최적해를 붙이면 전체의 최적해가 된다는 성질입니다. 이 성질이 있어야 남은 문제에도 같은 방식을 되풀이할 수 있습니다.

660원에서 500원을 넣으면 남은 문제는 160원을 가장 적은 동전으로 만드는 것입니다. 160원의 최적해는 동전 3개입니다. 여기에 500원 하나를 붙인 동전 4개가 660원의 최적해입니다.

동적 계획법도 최적 부분 구조에 기댑니다. 차이는 탐욕 선택 속성입니다. 동적 계획법은 어느 선택이 최적해로 이어질지 모른다고 봅니다. 그래서 선택마다 작은 문제를 다 풀어 표에 적어 둡니다. 그리디 알고리즘은 탐욕 선택 속성을 믿고 선택 하나만 따라갑니다.

회의실 배정과 기준 고르기

같은 문제라도 무엇을 「가장 좋아 보인다」로 삼느냐에 따라 답이 갈립니다. 이 소절은 회의실 하나에 회의를 가장 많이 넣는 회의실 배정 문제로 기준 셋을 비교합니다.

한 회의가 끝나기 전에 다른 회의가 시작하면 두 회의는 겹칩니다. 12시에 끝나는 회의와 12시에 시작하는 회의는 겹치지 않는다고 봅니다. 신청은 아래 네 건입니다.

A 는 하루를 거의 다 씁니다. Q 는 두 시간짜리로 가장 짧습니다. 이 네 건에 기준을 셋 바꿔 가며 그리디 알고리즘을 돌리면 아래와 같습니다.

가장 먼저 시작하는 A 를 고르면 나머지 셋이 모두 A 와 겹칩니다. 가장 짧은 Q 를 고르면 P 와 R 이 모두 Q 와 겹칩니다. 두 기준 모두 회의 하나로 끝납니다.

가장 먼저 끝나는 P 를 고르면 12시부터 방이 빕니다. Q 는 11시에 시작해 P 와 겹치므로 버립니다. R 은 12시에 시작하므로 넣습니다. A 는 겹치므로 버립니다. 회의 둘이 들어갑니다. 이것이 가장 많은 개수입니다.

교환 논증

기준이 몇몇 예에서 맞았다고 모든 입력에서 맞는 것은 아닙니다. 모든 입력에서 옳다는 것을 보이는 흔한 방법이 교환 논증(exchange argument)입니다. 이 방법은 먼저 최적해 하나를 잡습니다. 그 안의 선택을 그리디의 선택으로 바꿔도 답이 나빠지지 않는다는 것을 보입니다.

「가장 먼저 끝나는 회의」 기준에 대어 보면 이렇습니다.

1. 아무 최적해 하나를 잡습니다. 그 안에서 가장 먼저 끝나는 회의를 X 라고 합니다
2. 전체 신청 가운데 가장 먼저 끝나는 회의를 G 라고 합니다. G 는 X 보다 늦게 끝나지 않습니다
3. 최적해에서 X 를 빼고 G 를 넣습니다. 최적해의 나머지 회의는 모두 X 가 끝난 뒤 시작합니다. G 는 X 보다 늦게 끝나지 않으므로 그 회의들과 겹치지 않습니다
4. 회의 개수가 그대로이므로 바꾼 것도 최적해입니다

4번까지 오면 G 를 포함하는 최적해가 있다는 것이 나옵니다. 이것이 탐욕 선택 속성입니다.

G 를 넣고 나면 남은 문제는 G 가 끝난 뒤에 시작하는 회의들로 같은 문제를 푸는 것입니다. 이 작은 문제의 최적해에 G 를 붙이면 전체의 최적해가 됩니다. 이것이 최적 부분 구조입니다. 작은 문제에서도 가장 먼저 끝나는 회의를 고르면 되므로 그리디 알고리즘은 같은 기준을 끝까지 되풀이합니다.

그리디 방식으로 짠 알고리즘

그리디 방식으로 짜서 최적해를 보장하는 알고리즘 가운데 널리 쓰는 것을 모으면 아래 표와 같습니다. 저마다 앞의 교환 논증 같은 증명을 갖고 있습니다.

여러 지점을 선 비용 합이 가장 작게 잇는 문제를 최소 신장 트리 문제라고 부릅니다. 프림 알고리즘과 크루스칼 알고리즘은 같은 문제를 기준만 달리해 풉니다. 두 기준 모두 최적해를 냅니다.

비용

이 소절은 그리디 알고리즘의 계산량을 셉니다. 계산량은 대개 후보를 기준대로 늘어놓는 데서 나옵니다. 입력이 커질 때 계산량이 얼마나 빨리 느는지를 적는 표기가 빅오 표기법입니다.

후보 n 개를 기준대로 정렬하는 데 O(n log n) 이 듭니다. 정렬한 뒤 앞에서부터 한 번 훑는 데는 O(n) 이 듭니다. 그래서 회의실 배정은 전체가 O(n log n) 입니다.

프림 알고리즘과 다익스트라 알고리즘은 고르는 도중에 후보의 순서가 바뀝니다. 프림 알고리즘은 지점을 하나 이을 때마다 새로 붙일 수 있는 선이 생깁니다. 다익스트라 알고리즘은 거리를 하나 확정할 때마다 이웃한 곳까지의 거리가 줄어들 수 있습니다. 그래서 처음에 한 번 정렬해 둔 순서가 곧 맞지 않게 됩니다.

이럴 때는 우선순위 큐를 씁니다. 우선순위 큐는 들어 있는 값 가운데 우선순위가 가장 높은 값을 먼저 꺼내 주는 자료구조입니다. 새 후보가 생기면 큐에 넣습니다. 고를 때는 맨 앞 후보를 꺼냅니다. 꺼내고 넣을 때마다 O(log n) 이 듭니다.

완전 탐색과 비교하면 차이가 큽니다. 후보가 n 개면 넣고 빼는 조합이 2ⁿ 개입니다. n 이 30 이면 조합이 10억 개를 넘습니다. 같은 30 개를 정렬해 한 번 훑는 데는 비교가 200 번이 안 됩니다.

메모리도 적게 듭니다. 그리디 알고리즘은 지금까지 고른 것만 들고 다닙니다. 작은 문제의 답을 모두 표에 적어 두는 동적 계획법과 다른 점입니다.

최적해를 못 내도 쓰는 경우

이 소절은 탐욕 선택 속성이 없는 문제를 둘 봅니다. 하나는 문제를 조금 바꾸면 그리디가 맞는 경우입니다. 다른 하나는 그리디가 틀려도 대신 쓰는 경우입니다.

배낭 문제는 무게 한도가 있는 가방에 물건을 골라 담아 값의 합을 가장 크게 만드는 문제입니다. 가방 한도가 50 이고 물건이 아래 셋이라고 합니다.

무게 1 당 값이 큰 것부터 담으면 가와 나가 들어가 값이 160 입니다. 남은 무게 20 에는 다가 안 들어갑니다. 나와 다를 담으면 무게 50 에 값이 220 이므로 그리디의 답은 틀렸습니다.

물건을 쪼개 담을 수 있으면 결과가 달라집니다. 가와 나를 담은 뒤 다의 3분의 2 를 담으면 값이 80 늘어 240 이 됩니다. 이것이 최적해입니다. 쪼갤 수 있는 배낭 문제에는 탐욕 선택 속성이 있어 그리디가 맞습니다.

후보가 많아지면 최적해를 구하는 계산량이 감당 못 할 만큼 불어나는 문제도 있습니다. 모든 도시를 한 번씩 들르는 가장 짧은 길을 찾는 외판원 순회가 그런 예입니다. 이런 문제에서는 지금 있는 도시에서 가장 가까운 도시로 가는 그리디 방식을 최적해 대신 씁니다.

최적해를 보장하지 않지만 쓸 만한 답을 빨리 내는 방법을 휴리스틱이라고 합니다. 가장 가까운 도시로 가는 방식이 그런 예입니다. 그리디 방식은 휴리스틱을 짤 때 흔히 쓰입니다.

최적해를 보장하지 않는 알고리즘 가운데, 최적해보다 정해진 비율 이상 나빠지지 않는다는 것이 증명된 것은 근사 알고리즘이라고 따로 부릅니다. 그리디 방식으로 짠 근사 알고리즘도 흔합니다.

관련 항목

그리디 방식으로 푸는 알고리즘과 문제

프림 알고리즘 · 크루스칼 알고리즘 · 다익스트라 알고리즘 · 허프만 부호화 · 활동 선택 문제 · 최소 신장 트리 · 최단 경로 · 분할 가능 배낭 문제

그리디가 최적해를 내는 근거

탐욕 선택 속성 · 최적 부분 구조 · 교환 논증 · 매트로이드 · 컷 성질 · 최적해

그리디와 나란히 쓰는 설계 기법

동적 계획법 · 분할 정복 · 완전 탐색 · 재귀 백트래킹 · 분기 한정 · 메모이제이션

그리디가 최적해를 못 내는 문제

동전 교환 문제 · 배낭 문제 · 외판원 순회 · 집합 덮개 문제 · 그래프 색칠 문제

최적해 대신 그리디 답을 쓰는 기법

휴리스틱 · 근사 알고리즘 · 지역 최적해 · 언덕 오르기

그리디 알고리즘의 비용을 정하는 도구와 자료구조

빅오 표기법 · 시간 복잡도 · 정렬 · 우선순위 큐 · 힙

그리디 알고리즘이 속하는 상위 분류

알고리즘 · 알고리즘 설계 기법 · 그래프 알고리즘 · 최적화 문제