탐욕 알고리즘

각 단계에서 국소적으로 최적인 결정을 내리는 방식의 알고리즘 부류를 탐욕 알고리즘이라고 합니다. 국소적으로 최적인 해는 전역적으로 최적인 해보다 훨씬 쉽게 계산할 수 있으므로, 이러한 알고리즘은 보통 점근적 복잡도가 좋습니다.

어떤 경우에는 탐욕 알고리즘이 최적의 최종 해에 도달하지만, 그렇지 않은 경우도 있습니다. 탐욕 알고리즘을 고안하는 것, 특히 그 정당성을 증명하는 것은 매우 어려운 경우가 많습니다.

이 글에서는 탐욕 알고리즘으로 풀리는 문제의 고전적인 예시 몇 가지를 살펴보겠습니다.

#동전

문제. 어떤 국가의 화폐 체계는 액면가가 $a_1 = 1 < a_2 < a_3 < \ldots < a_n$인 동전들로 이루어져 있으며, 각 액면가는 바로 앞의 액면가로 나누어떨어집니다. 금액 $S$를 가능한 한 가장 적은 수의 동전으로 지불해야 합니다.

이 문제를 푸는 탐욕 알고리즘은 먼저 액면가 $a_n$인 동전을 가능한 한 많이(즉, $\lfloor \frac{S}{a_n} \rfloor$개) 취한 다음, 나머지 금액을 맞추기 위해 액면가 $a_{n-1}$인 동전을 가능한 한 많이 취하는 식으로 계속 진행하는 것입니다. $a_1 = 1$이므로 마지막에는 항상 필요한 금액을 맞출 수 있습니다.

a = [1, 2, 5, 10, 50, 100, 500, 1000, 2000, 5000]

def solution(s):
    coins = []
    for x in reversed(a):
        coins += [x] * (s // x)
        s %= x
    return coins

동전의 액면가가 서로 나누어떨어진다는 가정이 없으면 이 알고리즘이 항상 최적해를 출력하지는 않으며, 이 경우에는 문제를 동적 계획법으로 풀 수밖에 없습니다. 예를 들어, 1루블, 5루블, 7루블 동전으로 24루블을 거슬러 줄 때 탐욕 알고리즘은 $(7 \times 3 + 1 \times 3)$으로 바꾸지만, 최적해는 $(7 \times 2 + 5 \times 2)$입니다.

정당성. 귀류법으로 탐욕 알고리즘의 정당성을 증명합시다. 가장 큰 동전의 액면가가 $a_n < S$이지만 최적의 답에는 그 동전이 없다고 가정합시다.

최적의 답에서 액면가 $a_i$인 동전이 $b_i$번 등장했다고 합시다:

만약 $b_i \geq \frac{a_{i+1}}{a_i}$이면 $\frac{a_{i+1}}{a_i}$개의 동전을 액면가 $a_{i+1}$인 동전 하나로 바꿀 수 있으므로, 이는 최적의 답이 아닙니다. 따라서 $b_i \leq \frac{a_{i+1}}{a_i} - 1$입니다.

이제 최대 액면의 동전을 사용하지 않았을 때, 최적의 답에서 모든 동전의 액면 합이 최대 얼마가 될 수 있는지 계산해 봅시다:

따라서 $S \geq a_n$이면 최적의 답에는 항상 크기가 $a_k$인 가장 큰 동전을 넣어야 한다는 결론을 얻습니다. 그보다 작은 동전들만으로는 최적의 답에서 그만큼 큰 합을 만들 수 없기 때문입니다. 더 작은 동전들로 이루어진 집합에 대해서도 같은 방식으로 추론하면 모든 $S < a_n$에 대해서도 같은 결과를 얻으며, 이로부터 탐욕 알고리즘의 정당성이 따라 나옵니다.

또한 이 알고리즘은 서로 나누어떨어지는 액면가뿐만 아니라 다른 일부 경우에도 작동합니다. 이처럼 탐욕 알고리즘이 작동하는 화폐 체계를 정규 화폐 체계라고 부릅니다.

연습 문제. 이 알고리즘이 러시아 화폐 체계(1, 2, 5…)에서 올바르게 동작합니까?

#분할 가능한 물건이 있는 배낭

문제. 최대 $W$그램까지 담을 수 있는 배낭과, 무게가 $w_i$그램이고 그램당 가치가 $c_i$인 물건 $n$개가 있다고 합시다. 어떤 물건에서든 정수 그램만큼 잘라 낼 수 있습니다. 가치가 최대가 되도록 배낭을 채워야 합니다.

물건들을 ‘가치 밀도’ $\frac{c_i}{w_i}$의 내림차순으로 정렬하고, 이 순서대로 탐욕적으로 담겠습니다. 전부 들어가지 않는 마지막 물건은 일부만 담습니다.

정당성. 모든 물건을 머릿속으로 1그램씩 $w_i$개의 조각으로 나누면, 각 조각의 가치는 $\frac{c_i}{w_i}$가 됩니다. 무게가 모두 1그램으로 같은 조각들 중에서는 단순히 가치가 가장 큰 조각들을 고르는 것이 언제나 최적임이 분명하며, 이것이 바로 우리 알고리즘이 실제로 하는 일입니다.

최종 시간 복잡도는 정렬에 드는 $O(n \log n)$입니다.

#요청 선택

문제. 어떤 강의실에서 수업을 진행하겠다는 신청들이 주어집니다. 각 신청에는 수업의 시작 시각 $l_i$와 종료 시각 $r_i$가 명시되어 있습니다. 모든 신청 중에서 서로 겹치지 않도록 하면서 가능한 한 많은 신청을 남겨야 합니다.

여기서는 탐욕법이 그다지 자명하지 않게 됩니다. 신청을 어떤 순서로 살펴보아야 하는지, 그리고 신청을 어떻게 «탐욕적으로» 골라 담아야 하는지가 분명하지 않기 때문입니다.

종료 시각이 가장 이른 요청을 살펴봅시다. 이 요청은 항상 최적해에 포함하는 것이 이득이라는 점에 주목하십시오. 이 요청은 다른 모든 요청보다 먼저 끝나므로, 최적해에서 첫 번째 요청이 다른 요청이라면 그것을 종료 시각이 가장 이른 요청으로 아무 문제 없이 바꿀 수 있으며, 이때 새로운 겹침은 생기지 않습니다. 가장 첫 번째 요청을 더 왼쪽으로 옮긴 것에 불과하기 때문입니다.

종료 시각이 가장 이른 신청을 선택한 후에는 그것과 겹치는 신청을 모두 고려 대상에서 제외하고, 남은 신청 중에서 마찬가지로 종료 시각이 가장 이른 것을 선택한 뒤 다시 겹치는 신청을 모두 제외하는 식으로 신청이 남지 않을 때까지 반복합니다.

구현할 때는 구간을 명시적으로 삭제하지 않고, 구간을 끝나는 시간 기준으로 정렬한 뒤 마지막으로 선택한 일정이 끝나는 시간만 유지하는 것이 편리합니다.

struct activity {
    int l, r;
};

int solve(vector<activity> activities) {
    sort(activities.begin(), activities.end(), [](activity a, activity b) {
        return a.r < b.r;
    });
    int cnt = 0, last = 0;
    for (activity a : activities)
        if (a.l >= last)
            last = a.r, cnt++;
    return cnt;
}

시간 복잡도는 정렬에 드는 $O(n \log n)$입니다.