[Algorithm] 그리디 알고리즘(Greedy Algorithm) 완벽 가이드

그리디 알고리즘(Greedy Algorithm) 완벽 가이드

그리디는 사전적 의미로 탐욕스러운이라는 의미를 가집니다.

그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 좋아 보이는 선택을 반복적으로 수행하여 문제를 해결하는 알고리즘입니다. 최적의 해를 구하는 것이 목표지만, 매 단계마다 부분적인 최적의 선택을 한다는 것이 핵심입니다.

그리디 알고리즘의 기본 개념과 작동 원리

그리디 알고리즘은 문제 해결을 위해 전체적인 관점보다는 현재의 상황에서 가장 유리한 선택을 반복합니다.

다음과 같은 상황에서 사용될 수 있습니다

• 문제 분할 가능성(Divisible Subproblem) : 문제를 여러 작은 부분 문제로 나눌 수 있을 때
• 최적 부분 구조(Optimal Substructure) : 부분 문제의 최적해가 전체 문제의 최적해로 이어질 때
• 탐욕적 선택 속성(Greedy Choice Property) : 항상 지역 최적해가 전역 최적해를 보장할 때

작동 원리

• 현재 상황에서 가장 좋은 선택을 한다.
• 이 선택을 기반으로 다음 단계로 이동한다.
• 과정을 반복하여 문제를 해결한다.

그리디 알고리즘의 장점과 특징

• 단순성(Simple Implementation) : 알고리즘이 비교적 간단하며, 빠르게 구현할 수 있습니다.
• 빠른 계산 속도(Efficiency) : 대부분 O(n log n) 또는 O(n)의 시간 복잡도를 가지므로 매우 빠릅니다.
• 적용 가능 문제의 범위가 넓음(Wide Applicability) : 스케줄링, 네트워크 연결, 최단 경로 등 다양한 문제에 적용할 수 있습니다.

그리디 알고리즘의 예시 문제와 자바 구현

예제 1 : 동전 거스름돈 문제

가장 적은 수의 동전을 사용하여 특정 금액을 거슬러 줘야 하는 문제입니다.

예를 들어, 500원, 100원, 50원, 10원의 동전이 있을 때, 1260원을 거슬러 줄 때 최소 동전의 개수를 구합니다.

• 문제 분석 : 각 단계에서 가장 큰 단위의 동전부터 차례로 선택하는 것이 최선입니다.
• 알고리즘 적용 조건 : 그리디 알고리즘이 최적의 해를 보장할 수 있는 경우는 각 동전이 다른 동전의 배수일 때입니다.

public class CoinChange {
    public static void main(String[] args) {
        int payBack = 1260; // 거슬러 줘야 할 금액
        int count = 0; // 동전의 개수
        int[] coins = {500, 100, 50, 10}; // 동전의 종류

        for (int coin : coins) {
            count += payBack / coin; // 해당 동전으로 나눌 수 있는 최대 개수를 더함
            payBack %= coin; // 나머지 금액 갱신
        }

        System.out.println("필요한 동전의 최소 개수: " + count);
        // 필요한 동전의 최소 개수: 6개 (500원 2개, 100원 2개, 50원 1개, 10원 1개)
    }
}

예제 2: 활동 선택 문제

다양한 활동이 시작 시간과 종료 시간으로 표현될 때, 한 사람이 최대한 많은 활동을 할 수 있도록 선택하는 문제입니다.

• 문제 분석 : 종료 시간이 빠른 활동부터 선택하는 것이 최적입니다.
• 알고리즘 적용 조건 : 활동이 종료 시간이 빠른 순서대로 정렬되어 있을 때입니다.

import java.util.Arrays;
import java.util.Comparator;

public class ActivitySelection {
    static class Activity {
        int start;
        int end;

        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 4),
            new Activity(3, 5),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(3, 9),
            new Activity(5, 9),
            new Activity(6, 10),
            new Activity(8, 11),
            new Activity(8, 12),
            new Activity(2, 14),
            new Activity(12, 16)
        };

        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));

        int count = 0;
        int lastEnd = 0;

        for (Activity activity : activities) {
            if (activity.start >= lastEnd) {
                count++;
                lastEnd = activity.end;
            }
        }

        System.out.println("선택된 활동의 최대 개수: " + count);
        // 선택된 활동의 최대 개수: 4개
    }
}

그리디 알고리즘의 한계

• 최적해 보장 불가(Not Always Optimal) : 모든 문제에 대해 최적해를 보장하지는 않습니다. 예를 들어, 0/1 배낭 문제(Knapsack Problem)와 같은 경우에는 최적해를 보장하지 못합니다.
• 문제 특성 의존성(Problem Specificity) : 문제의 특성에 따라 그리디 알고리즘의 유효성이 결정됩니다. 그리디 선택이 항상 전역 최적해로 이어지지는 않습니다.

그리디 알고리즘을 사용하지 못하는 경우

• 0/1 배낭 문제(Knapsack Problem) : 물건을 쪼갤 수 없는 상황에서, 그리디하게 가벼운 것부터 선택하면 최적의 해를 구하지 못할 수 있습니다. 이런 문제는 동적 프로그래밍을 사용하는 것이 일반적입니다.

그리디 알고리즘 vs 다른 알고리즘

비교 항목그리디 알고리즘동적 프로그래밍(Dynamic Programming)분할 정복(Divide and Conquer)

접근 방식	현재 최적의 선택	최적 부분 문제를 저장하며 최적해 구함	문제를 분할하고 각각의 문제를 독립적으로 해결
최적해 보장 여부	특정 문제에서만 보장	모든 문제에서 최적해 보장	모든 문제에서 최적해 보장
시간 복잡도	일반적으로 O(n log n) 또는 O(n)	O(n^2) 또는 그 이상	O(n log n)
구현 난이도	상대적으로 쉬움	다소 복잡함	문제에 따라 다름

결론과 적용 팁

그리디 알고리즘은 문제 해결의 직관적인 접근 방식으로, 적절한 문제에서는 빠르고 효과적인 솔루션을 제공합니다. 그러나 모든 문제에 최적의 해를 보장하지는 않으므로, 문제의 특성을 잘 이해하고 그리디 알고리즘이 적합한지 판단하는 것이 중요합니다. 또한, 동적 프로그래밍, 분할 정복 등의 다른 알고리즘과 함께 사용하여 최적의 솔루션을 찾는 것이 좋습니다.