[알고리즘] 그리디 알고리즘(Greedy Algorithm)

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

※ 해당 포스팅은 하기 출처들을 참조하였습니다.

- 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022

 

 

 

이번 포스팅에서는 그리디 알고리즘(Greedy Algorithm)에 대해 알아보겠습니다.

1. 개요

 그리디 알고리즘(Greedy Algorithm)은 우리말로 탐욕법이라고도 하며, 현재 가장 좋다고 판단되는 값을 우선적으로 취하고 이를 반복하여 가장 좋은 결과를 도출해내는 방식입니다.

 

그림 1. 은행 창구 대기열

 그림 1은 은행의 각 창구의 손님들의 대기열을 도식화 한 것입니다. 각 사각형은 손님을 나타내며, 안의 숫자는 해당 손님이 업무를 보는데 소요되는 시간(분)을 나타냅니다. A 창구에서 가까운 손님부터 현재 순서 그대로 업무를 볼 경우, 두번째 손님의 대기 시간은 10분, 세번째 손님은 15분, ... , 마지막 손님은 무려 56분이나 대기해야 됩니다. 7명의 평균 대기시간만 해도 25분 가까이 걸리며, B 창구의 평균 대기시간은 무려 38분에 달합니다.

 

그림 2. 은행 창구 대기열 (내림차순 정렬)

 그림 2는 그림 1의 대기열에서 업무 소요시간이 적은 순으로 정렬한 모습입니다. 이처럼 소요시간이 적은 손님부터 처리하면 평균 대기시간을 크게 줄일 수 있습니다. A창구의 경우 평균 대기시간이 25분 남짓에서 19분으로 줄어들며, B 창구의 경우 무려 38분에서 23분 조금 넘는 정도로 크게 줄어듭니다. 해당 예시의 경우 가장 적은 소요시간이 필요한 손님을 먼저 처리하는 것을 최적의 판단이라고 보고, 이를 반복하여 최선의 결과를 도출해내는 그리디 알고리즘의 예시라고 할 수 있겠습니다.

 

 단, 그리디 알고리즘을 적용하려면 해당 문제가 다음의 두가지 속성을 만족해야 합니다.

 

- 1) 그리디 선택(Greedy Choice) : 현재 선택이 이후의 선택에 영향을 미치지 않음

- 2) 최적 부분구조(Obtimal Substructrure) : 해당 문제의 최적의 솔루션이 부분 문제들의 솔루션으로 구성됨

 

 위의 예시를 보면 누가 먼저 업무를 보더라도 다른 손님의 업무 소요 시간에 영향을 주지 않으므로 그리디 선택 조건을 만족합니다. 또한 A그룹을 예시로 들면, 손님 그룹을 {4, 5, 7, 8},  {10, 12, 16}으로 나누어도 각 부분집합의 최적해는 동일하고, 이를 합치면 전체 A 그룹의 최적해가 됩니다.

 

해당 조건들을 불만족하는 대표적인 예시로 '배낭 문제'가 있습니다.

 

그림 3. 배낭 문제

 위와 같이 각 상품의 무게와 가격이 있고, 배낭에 넣은 상품들의 가격의 합이 가장 크게 만드려는 상황을 가정해봅시다. 단, 배낭에 넣을 수 있는 무게에는 최대치가 존재하고 이를 넘어가서는 안됩니다. 이 문제 또한 단위 무게당 가격을 계산하여 가장 높은 값부터 추가하는 식으로 그리드 알고리즘을 적용할 수 있을거 같지만, 실상은 조금 다릅니다. 예를 들어서 배낭의 한도가 6kg인 상황을 생각해봅시다.

 

그림 4. 배낭 문제 - 6kg 제한일 경우

 무게당 가격이 가장 높은 상품은 1번, 2번, 4번 상품이며, 그 중 가격이 가장 높은 4번 상품을 넣을 경우 1kg이 남으므로 7번 상품만 넣을 수 있습니다. 이와 다르게 무게당 가격이 가장 높은 상품 중, 무게가 낮은 순서대로 추가할 경우 1번, 2번 상품 순으로 넣게 되고, 1kg이 남으므로 마찬가지로 7번 상품만 넣을 수 있습니다. 두 경우 모두 상품의 최종 가격은 28만원입니다.

 

 허나 실제로 이 상황에서 만들 수 있는 최대 가격은 29만원으로, 2번 상품과 6번 상품을 골랐을 경우입니다. 해당 문제는 배낭의 최대 무게를 고려해야 하기 때문에(greedy choice 불만족), 물건의 가격이나 무게당 가격 등을 기준으로 최선의 선택을 반복해도 최선의 결과로 도달하지 못하는 것입니다. 이와 같은 문제에 그리드 알고리즘을 적용하려면, 배낭에 상품을 넣을 때 단위 무게로 나눌 수 있어야 합니다(여담으로 이런 문제를 '분할 가능한 배낭 문제'라고 합니다).

 

 

2. 코드 예시

 다음은 그림1과 그림2의 예시를 간단하게 C# 코드로 작성한 것입니다.

class Program
{
    static void Main(string[] args)
    {
        int[] A = { 10, 5, 7, 12, 4, 16, 8 };
        int[] B = { 19, 9, 12, 6, 15, 11, 4 };

        Console.WriteLine($"A 창구의 평균 대기 시간: {string.Format("{0:0.00}", AverageTime(A))}분");
        Console.WriteLine($"B 창구의 평균 대기 시간: {string.Format("{0:0.00}", AverageTime(B))}분");

        Console.WriteLine("\n--------정렬 후--------\n");
        Array.Sort(A);
        Array.Sort(B);

        Console.WriteLine($"A 창구의 평균 대기 시간: {string.Format("{0:0.00}", AverageTime(A))}분");
        Console.WriteLine($"B 창구의 평균 대기 시간: {string.Format("{0:0.00}", AverageTime(B))}분");
    }

    static float AverageTime(int[] target)
    {
        float count = 0;
        int last = target.Length - 1;
        for (int i = 0; i < last; i++)
            count += target[i] * (last - i);

        return count / target.Length;
    }
}

사진 1. 창구 문제 결과

 그림1의 창구 A, B를 배열로 표현하였고, 해당 배열의 순서대로 처리 시 전체 인원의 평균 대기시간을 계산하는 함수를 정의하여 사용했습니다. 위에서 알아본 바와 마찬가지로 평균 대기시간이 약 24.71분, 38분 걸리지만, 오름차순으로 정렬한 후에는 19분, 약 23.14분으로 줄어든 것을 알 수 있습니다. 

 

 실제 문제는 물론 이것보다는 복잡한 경우가 많습니다. 앞서 얘기했던 분할 가능한 배낭 문제의 경우, 각 상품의 단위 무게당 가격을 계산한 뒤에 해당 값을 기준으로 최선의 값을 취해야 합니다. 중요한 점은 가장 좋은 값을 취한다는 그리디 알고리즘의 특성상, 정렬을 사용할 확률이 높다는 것입니다. 정렬은 단순 버블 정렬(Bubble Sorting)의 경우 시간복잡도가 O(n²)에 달하는 등 비용이 높은 연산이므로, 가능한 한 정렬 비용을 줄이는 것이 좋습니다.

 

 정렬 비용을 줄이기 위해 경우에 따라 우선순위 큐(Priority Queue)를 사용할 수 있습니다. 우선순위 큐는 내부적으로 힙 정렬(Heap Sorting)을 이용하는데, O(n*log(n))의 시간복잡도로 동작하므로 단순 정렬 알고리즘보다는 빠르게 동작합니다. 이를 활용한 알고리즘이 지난 포스팅에서 알아본 A* 알고리즘으로, 각 정점의 최종 예상 비용을 우선순위 큐에 저장함으로서 다음에 방문할 정점을 신속하게 찾아냅니다. 다익스트라 및 A* 알고리즘도 아직 방문하지 않은 정점 중 값(예상 비용)이 가장 낮은 정점을 선택하여 방문하고, 이를 반복하므로 그리드 알고리즘에 속한다고 볼 수 있습니다.

 

 

3. 장단점

 그리디 알고리즘의 단점은 적용할 수 있다는 문제의 폭이 좁다는 점입니다. 앞서 알아보았듯이 그리디 알고리즘은 최적 부분 구조와 그리디 선택 속성을 갖는 문제에만 적용할 수 있기 때문에, 해당 문제가 조건을 만족하지 않는다면 아예 적용을 할 수 없습니다.

 

 하지만 이런 단점을 갖는 대신, 조건만 만족하면 빠르게 최적의 결과를 도출해낼 수 있다는 장점이 있습니다. 앞에서 얘기한 배낭 문제의 경우, 그리디 알고리즘을 적용할 수 없으므로 가능한 모든 경우의 수를 계산하여 가장 비용이 높은 결과를 찾아내야 합니다. 물론 이런 경우에는 중간 계산값을 이용해 계산을 최적화하는 동적 계획법(Dynamic Programming)을 사용할 수 있지만, 분할 가능한 배낭 문제에 그리디 알고리즘을 적용하는 경우보다는 느립니다. 따라서 현재 직면한 문제가 조건을 만족한다고 판단될 경우, 그리디 알고리즘을 적용하는 것이 효과적일 수 있습니다.