[알고리즘 정리] 그리디 알고리즘(Greedy Alogorithm)

Greedy Algorithm

탐욕 알고리즘이라고 부르기도 하는 그리디 알고리즘은 문제를 단계적으로 해결하면서, 한 단계마다 그 순간의 최선의 solution 이라고 생각되는 solution을 선택해서 최종적인 solution을 찾아가는 알고리즘 전략이다.

Local Optimum and Global Optimum Solution

이때 어떤 단계에서 보이는 최선의 solution을 local optimum 이라고 하고, 전체 문제에 대한 최적의 solution을 global optimum 이라고 한다. 하지만 모든 문제가 local optimum을 통해 global optimum을 만들 수 있지는 않다. 우리가 인생을 살면서 현재 순간에 최선의 선택을 했다고 생각하지만 나중에 지나고보면 그게 최선이 아닐 때가 많지 않은가..

Coin Change Problem

가장 간단하게 그리디 알고리즘을 적용할 수 있는 문제가 Coin Exchange Problem 이다. 어떤 가게에서 거스름 돈을 건네준다고 할 때, 그 가게는 최소한의 동전 갯수로 거스름 돈을 주기를 원할 것이다.

 

그럼 최소한의 동전만 사용하면서 거스름돈을 줄 수 있는 방법이 무엇이 있을까? 다음 예시를 보자.

• 문제: 우리가 가지고 있는 동전은 0.5, 0.25, 0.1, 0.05, 0.01 라고 하자. 거슬러줘야 할 돈이 0.74일 때 동전 갯수를 최소한으로 사용하면서 줄 수 있는 방법은?
• 해결방법: 너무나 상식적으로 생각해보면 그냥 가장 값이 큰 동전을 우선적으로 사용하면 된다. 따라서 0.5 한 개, 0.1 두 개, 0.01 네 개를 사용하면 최소한의 갯수로 해결할 수 있을 것이다.

위 해결 방법은 그리디 알고리즘을 적용한 예이다. 0.5 짜리 동전을 선택했을 때 최선의 경우는 0.5 짜리 하나를 내는 것이다. 그리고 남은 돈을 거슬러줄 때 0.25 에서 줄 수 있는 최선의 경우는 0, 0.1에서는 2 ... 이런식으로 단계마다 최선의 경우를 선택하다보면 문제를 해결하게 된다.

Activity Selection Problem

동전 교환 문제는 너무 쉬웠으니까, 좀 더 복잡한 문제를 살펴보자. Activity Selection Problem 은 어떤 여러 활동들의 시작 시간과 끝나는 시간이 주어져 있을 때, 주어진 어떤 시간 안에 할 수 있는 활동을 최대한 많이 배치하는 방법을 찾는 문제이다.

Theorem

그리디 알고리즘을 적용하기 위해서는 다이나믹 프로그래밍에서 했던 것 처럼, 이 문제가 optimal substructure를 가지고 있는지 먼저 확인하는 과정을 거쳐야한다.

• 우리에게 활동들의 집합인 S_ij 가 있다고 하고, 해당 집합은 공집합이 아니라고 가정해보자. S_ij 의 i는 S 전체에 대한 시작시간, j는 S 전체에 대한 끝나는 시간을 의미한다고 하자.
• a_m 을 설정하고 이 변수가 S_ij 안에 있는 활동들을 최대한 많이 배치한 갯수 라고 한다면,
• S_im, 즉 최대한 많이 배치했을 때의 시작시간과 S의 시작 시간 사이에는 어떤 활동도 존재하지 않을 것이다. 왜냐하면, 우리는 이미 a_m 을 최대 갯수로 설정했기 떄문이다.
• 따라서, 어떤 순간의 최적의 배치인 a_m 을 찾는 다면 전체 문제였던 S_ij 는 a_m이 끝나는 시간부터 S가 끝나는 시간 사이에 있는 최대 배치를 찾는 문제로 문제가 작아지게 된다. 즉 이 문제는 optimal substructure 를 가지게 된다는 뜻이다.

Solution

그렇다면 어떤 구간에서 최대한으로 활동을 많이 배치할 수 있는 방법을 찾아보자. 동전 교환문제와 비슷한 방법으로 접근할 수 있다. 문제를 가장 끝 substructure까지 쪼개어보면 결국 제일 마지막에는 이전 활동과 이어붙일 수 있는 활동 중에서 끝나는 시간이 가장 짧은 활동이 될 것이다. 끝나는 시간이 가장 빠른 활동을 앞에, 그리고 그 끝나는 시간 이후에 가장 빨리 시작할 수 있는 활동 중 끝나는 시간이 가장 빠른 활동을 골라 바로 시작하면 최대한 많은 활동들을 나열 할 수 있을 것이다. 따라서 우리는 한 활동이 끝났을 때 고를 수 있는 최선의 활동(local optimum)을 고르면 되는 것이다.

 

이를 위해서 일반적으로 그리디 알고리즘을 위해서 key가 되는 값, Activity Selection Problem 같은 문제에서는 끝나는 시간을 기준으로 전체를 소팅한 후에 활동들을 찾아간다.

Example Problem

[백준 알고리즘] 알고리즘의 1931번에 회의실을 배정하는 문제가 있다. 다른 포스트에서 정리했던 부분이니 그대로 이곳에 덧붙이도록 하겠다.

문제

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

풀이

회의 시간을 최대한 촘촘히 배정하려면, 끝나는 시간이 제일 빠른 순서대로 사용시간을 따닥따닥 붙여주면 된다. 현재기준으로 끝나는 시간이 제일 빠른 구성을 선택하면 최대 갯수를 맞출 수 있을 것이다.
하나의 최선의 선택을 하고 나면 남은 시간들 속에서 또 최선의 구성을 선택해야되는 문제가 되니 문제의 크기가 계속 줄어들게 된다.

그리디 알고리즘은 주어진 배열을 미리 정렬해두고 순회하는 방법으로 문제를 해결하는데, 이번 문제에서 생각했어야하는 부분은 배열을 정렬할 때, 끝나는 시간이 여러개가 겹칠 경우 최적의 값을 얻지 못한다는 것이다.

index	0	1	2	3	4	5
start time	1	2	5	4	7	8
finish time	1	4	7	7	7	8

끝나는 시간을 기준으로 정렬을 했을 때, 다음과 같이 정렬되었다고 하자, 이 구성에서 회의실을 배정해보면,

0번째 구성이 끝나자마자 시작할 수 있는 제일 끝나는 시간이 빠른 1번 구성을 선택,
1번 구성이 끝나자마자 시작할 수 있는 제일 끝나는 시간이 빠른 구성인 2번을 선택,
3번은 끝나는 시간과 시작하는 시간이 안맞기 때문에 건너뛰고 4번을 선택,
마지막으로 5번을 선택하게 된다.

 

따라서 배정할 수 있는 회의실의 최대 갯수가 총 5개가 되는데, 사실은 그렇지 않다. 2번 인덱스와 3번인덱스를 교체해주면 배정할 수 있는 회의가 하나 늘어나기 때문이다.

index	0	1	2	3	4	5
start time	1	2	4	5	7	8
finish time	1	4	7	7	7	8

위 구성으로 배열이 정렬된다면 6개의 회의실을 배정할 수 있게된다. 따라서 끝나는 시간을 기준으로 정렬할 때, 같은 값이 나오면 시작시간을 비교해서 더 빠른 시간을 앞에 두어야 한다.

 

이 문제를 풀 때는 pair, vector 를 이용해서 회의시간을 짝지어서 담고 정렬을 거친 뒤 for문으로 순회하는 방식을 사용했다.

std::sort가 기본적으로 지원하는 속도가 n log n 이기 때문에 최악의 경우에도 배열 전체를 순회하는 속도가 n 이기 때문에 O(nlogn)으로 해결할 수 있다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

bool pairSecondLess(const pair<int, int> &a, const pair<int, int> &b)
{
    if (a.second == b.second)
    {
        return a.first < b.first; // second 가 같으면 first가 작은 놈이 더 작다!
    }
    return (a.second < b.second);
}

int main()
{
    int N;
    scanf("%d", &N);
    vector<pair<int, int>> greedy;

    for (int i = 0; i < N; i++)
    {
        int s, f;
        scanf("%d %d", &s, &f);
        greedy.push_back(make_pair(s, f));
    }

    sort(greedy.begin(), greedy.end(), pairSecondLess); // 정렬할 때 인자로 위에서 정의한 함수를 준다.

    vector<pair<int, int>> v;
    v.push_back(greedy[0]); // 제일 처음은 끝나는 시간이 제일 빠른 구성이 들어간다.
    for (int i = 1; i < greedy.size(); i++)
    {
        if (v.back().second <= greedy[i].first) // 가장 마지막 최적의 구성과 비교
        {
            v.push_back(greedy[i]); // 현재 최선의 배정이 가진 끝나는 시간 이후에 시작할 수 있는 시간 중 끝나는 시간이 제일 빠른 구성을 넣어준다.
        }
    }

    printf("%ld", v.size());
}