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

 

 

 

 

그리디 알고리즘에 대해 알아보기

---

 

 

 

 

그리디 알고리즘(Greedy Algorithm)이란 문제를 해결할 때마다 현재 상황에서 가장 최적이라고 생각되는 선택을 하는 방식을 통해 전체 문제를 해결하는 알고리즘입니다. 그리디 알고리즘은 많은 최적화 문제를 빨리 해결할 수 있고 직관적이며 구현이 간단한 경우가 많습니다. 하지만 항상 최적의 해를 보장하지 않기 때문에 주의해야 합니다. 

 

 

 

기본 개념

• 현재 선택이 최적 : 각 단계에서 가장 최적이라고 생각되는 선택을 함
• 결과가 최적 : 전체 결과가 최적의 해를 이루어야 함

 

 

장점

• 간단한 구현 : 그리디 알고리즘은 비교적 간단하게 구현할 수 있음
• 빠른 실행 : 대부분의 그리디 알고리즘은 반복문을 사용하여 선형 시간 안에 해결할 수 있음 
• 효율성 : 자주 최적의 해를 구할 수 있음 특히 최적 부분 구조(Optimal Substructure)와 탐욕 선택 속성(Greedy Choice Property)을 가지는 문제에서 효과적임

단점

• 최적 해를 보장하지 않음 : 항상 최적의 해를 구하는 것은 아니기 때문에 그리디 알고리즘이 문제에 적합한지 신중하게 고려해야 함
• 문제 특화 : 특정 문제에만 적용 가능하며, 모든 문제에 적용할 수 있는 만능 알고리즘은 아님 

 

 

예제

 

대표적인 그리디 알고리즘 문제로는 거스름돈 문제, 활동 선택 문제, 최소 스패닝 트리 등이 있습니다. 

 

 

1. 거스름돈 문제

거스름돈 문제는 다양한 동전 단위가 주어졌을 때, 특정 금액을 만들기 위해 최소한의 동전 개수를 사용하는 문제입니다.

문제 설명

• 입력 : 동전 단위와 거스름돈 금액
• 출력 : 최소 동전 개수와 사용된 동전 단위

import java.util.Arrays;

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
        int amount = 289;

        System.out.println("Minimum coins required: " + getMinimumCoins(coins, amount));
    }

    public static int getMinimumCoins(int[] coins, int amount) {
        Arrays.sort(coins);
        int count = 0;

        for (int i = coins.length - 1; i >= 0; i--) {
            if (amount >= coins[i]) {
                count += amount / coins[i];
                amount = amount % coins[i];
            }
        }
        return count;
    }
}

 

 

 

 

2. 활동 선택 문제

 

활동 선택 문제는 각 활동이 시작 시간과 종료 시간을 가지고 있으며, 활동들이 겹치지 않도록 최대한 많은 활동을 선택하는 문제입니다.

문제 설명

• 입력: 각 활동의 시작 시간과 종료 시간
• 출력: 최대한 많은 활동의 집합

import java.util.*;

class Activity implements Comparable<Activity> {
    int start, finish;

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

    @Override
    public int compareTo(Activity other) {
        return this.finish - other.finish;
    }
}

public class ActivitySelection {
    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, 8),
            new Activity(5, 9),
            new Activity(6, 10),
            new Activity(8, 11),
            new Activity(8, 12),
            new Activity(2, 13),
            new Activity(12, 14)
        };

        System.out.println("Maximum number of activities: " + selectActivities(activities));
    }

    public static int selectActivities(Activity[] activities) {
        Arrays.sort(activities);
        int count = 1;
        int lastFinishTime = activities[0].finish;

        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastFinishTime) {
                count++;
                lastFinishTime = activities[i].finish;
            }
        }
        return count;
    }
}