탐욕 알고리즘

탐욕 알고리즘(Greedy Algorithm)은 문제를 해결하기 위해 현재 단계에서 가장 최적인 선택을 반복적으로 수행하여, 최적의 해를 찾아가는 알고리즘입니다. 탐욕 알고리즘은 비교적 단순한 구현 방식과 빠른 연산 속도를 제공하기 때문에 다양한 최적화 문제에서 널리 사용됩니다.

이 포스팅에서는 탐욕 알고리즘의 기본 개념, 탐욕 알고리즘이 활용되는 대표적인 문제 유형, 구현 예시 등을 알아보겠습니다.

---

1. 탐욕 알고리즘이란?

탐욕 알고리즘은 매 순간 가장 최적의 선택을 수행하여 문제를 해결해 나가는 방법입니다. 이때 각 단계에서의 선택은 전체 문제를 해결하는 데 영향을 미치며, 이러한 선택이 누적되면서 전역 최적해에 도달하게 됩니다.

탐욕 알고리즘은 최적 부분 구조와 탐욕적 선택 속성이라는 두 가지 특징을 가지고 있습니다.

• 최적 부분 구조: 문제의 최적해는 부분 문제들의 최적해로 구성됩니다.
• 탐욕적 선택 속성: 문제를 해결할 때, 각 단계에서 탐욕적으로 선택해도 최종 해에 도달할 수 있습니다.

이 두 가지 속성을 만족하는 경우, 탐욕 알고리즘을 통해 문제를 효과적으로 해결할 수 있습니다.

---

2. 탐욕 알고리즘의 대표적인 문제

탐욕 알고리즘은 다양한 최적화 문제에서 사용되며, 아래와 같은 대표적인 문제들이 있습니다.

2.1. 거스름돈 문제

주어진 금액을 최소 개수의 동전으로 거슬러 주는 문제입니다. 예를 들어, 500원, 100원, 50원, 10원 동전으로 거슬러 줄 때, 가장 큰 단위부터 채워나가면 최소 개수의 동전으로 거스름돈을 만들 수 있습니다.

2.2. 활동 선택 문제

여러 개의 활동들이 주어졌을 때, 일정 시간 내에 최대한 많은 활동을 수행하고자 할 때 사용됩니다. 각 활동의 시작과 종료 시간이 주어지면, 종료 시간이 빠른 순서대로 선택하여 최대 개수의 활동을 할 수 있습니다.

2.3. 배낭 문제(Knapsack Problem)

물건의 가치와 무게가 주어진 상황에서, 정해진 무게를 초과하지 않도록 하면서 가장 높은 가치를 얻을 수 있도록 물건을 선택하는 문제입니다. 이 문제는 정수 배낭 문제와 분수 배낭 문제로 나뉘며, 탐욕 알고리즘은 분수 배낭 문제에 적합합니다.

2.4. 최소 신장 트리(Minimum Spanning Tree)

크루스칼 알고리즘과 프림 알고리즘은 탐욕 알고리즘의 대표적인 예로, 가중치가 있는 그래프에서 모든 정점을 최소 비용으로 연결할 수 있는 트리를 만드는 문제입니다.

---

3. 탐욕 알고리즘의 구현 예시 (c#)

3.1. 거스름돈 문제 예시

다음은 거스름돈을 최소 개수의 동전으로 주는 Python 구현 예시입니다.

using System;
using System.Collections.Generic;

public class GreedyAlgorithm
{
    public static int GetMinCoins(int change, List<int> coins)
    {
        coins.Sort((a, b) => b.CompareTo(a)); // 동전을 내림차순 정렬
        int count = 0;

        foreach (var coin in coins)
        {
            count += change / coin;
            change %= coin;
        }

        return count;
    }

    public static void Main()
    {
        int change = 860; // 거스름돈
        List<int> coins = new List<int> { 500, 100, 50, 10 }; // 동전 단위
        Console.WriteLine($"최소 동전 개수: {GetMinCoins(change, coins)}");
    }
}

이 코드에서는 가장 큰 단위의 동전부터 차례로 거슬러 줍니다. 500원 동전부터 채워나가기 때문에 최소 개수의 동전으로 거스름돈을 줄 수 있습니다.

3.2. 활동 선택 문제 예시

다음은 활동 선택 문제를 해결하는 Python 구현 예시입니다.

using System;
using System.Collections.Generic;
using System.Linq;

public class ActivitySelection
{
    public static List<(int start, int end)> MaxActivities(List<(int start, int end)> activities)
    {
        // 종료 시간을 기준으로 활동 정렬
        activities.Sort((a, b) => a.end.CompareTo(b.end));
        List<(int start, int end)> selected = new List<(int start, int end)>();

        // 첫 활동 선택
        selected.Add(activities[0]);
        for (int i = 1; i < activities.Count; i++)
        {
            // 이전 활동의 종료 시간 이후 시작하는 활동만 추가
            if (activities[i].start >= selected.Last().end)
            {
                selected.Add(activities[i]);
            }
        }

        return selected;
    }

    public static void Main()
    {
        List<(int start, int end)> activities = new List<(int start, int end)>
        {
            (1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)
        };

        var selectedActivities = MaxActivities(activities);
        Console.WriteLine("선택된 활동:");
        foreach (var activity in selectedActivities)
        {
            Console.WriteLine($"활동 시작: {activity.start}, 종료: {activity.end}");
        }
    }
}

이 코드에서는 각 활동을 종료 시간 기준으로 정렬한 후, 겹치지 않는 활동을 선택하여 최대 활동 개수를 구할 수 있습니다.

---

4. 탐욕 알고리즘의 장점과 단점

장점

• 단순하고 빠름: 구현이 간단하고, 대부분 O(n log n) 또는 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.
• 효율성: 매 순간 최적의 선택을 하기 때문에 부분 문제를 다시 계산할 필요가 없습니다.

단점

• 전역 최적해를 보장하지 않음: 모든 문제에서 항상 최적해를 구하는 것은 아니며, 문제의 특성에 따라 근사해를 구할 수밖에 없는 경우도 있습니다.
• 탐욕적 선택이 불가능한 경우: 일부 문제에서는 현재 단계의 선택이 전역 최적해를 보장하지 않기 때문에 탐욕 알고리즘을 사용할 수 없습니다.

---

5. 탐욕 알고리즘이 적합한 문제의 특성

탐욕 알고리즘이 효과적으로 작동하기 위해서는 다음과 같은 두 가지 특성을 만족해야 합니다.

• 최적 부분 구조: 문제의 최적해가 부분 문제의 최적해로 구성되는 경우
• 탐욕적 선택 속성: 매 단계의 탐욕적 선택이 전역 최적해로 확장 가능한 경우

이 두 가지 특성을 확인하여 탐욕 알고리즘이 적합한지 판단할 수 있습니다.

---

탐욕 알고리즘은 다양한 최적화 문제에서 유용하게 사용되며, 매 순간 최적의 선택을 하는 단순하고 직관적인 알고리즘입니다. 거스름돈 문제, 활동 선택 문제, 배낭 문제 등 여러 문제에서 자주 활용되며, 효율적인 문제 해결에 강력한 도구가 됩니다. 탐욕 알고리즘의 특성을 이해하고, 적절한 문제에 활용할 수 있는 능력은 알고리즘 최적화와 문제 해결력을 크게 향상시켜줄 것입니다.