그리디(Greedy)

1. 그리디(Greedy) 알고리즘이란?

- 그리디 알고리즘은 매 단계마다 현재 상황에서 가장 최적인 선택을 하는 알고리즘이다.

- 매 단계마다 최선이라고 판단을 하는 지역 최적 선택(Local Optimal Choice)를 반복하여 전역 최적해(Global Optimal Solution)에 도달하려고 한다.

- 구현이 단순하며, 문제의 구조를 직관적으로 이해할 수 있다.

- 항상 전역 최적해를 보장하지는 않으므로, 문제에 따라서는 그리디 접근이 근사해만 제공할 수 있다.

 

2. 그리디 알고리즘 구현

2-1. 활동 선택 문제

- 여러 활동들이 시작 시간과 종료 시간을 가지고 주어질 때, 서로 겹치지 않게 선택할 수 있는 활동의 최대 개수를 구하는 문제이다.

public class ActivitySelection {
    // 활동 배열에서 겹치지 않는 최대 활동 수를 반환하는 함수
    public static int maxActivities(Activity[] activities) {
        // 활동들을 종료 시간 기준으로 오름차순 정렬
        Arrays.sort(activities, new Comparator<Activity>() {
            @Override
            public int compare(Activity a, Activity b) {
                return a.finish - b.finish;
            }
        });

        // 첫 번째 활동 선택
        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;
    }

    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)
        };

        int max = maxActivities(activities);

        // 출력: 4
        System.out.println(max);
    }
}

class Activity {
    int start;
    int finish;

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

 

2-2. 배낭 문제

- 배낭의 용량을 최대한 활용하여 전체 가치를 최대로 만드는 문제이다.

public class FractionalKnapsack {
    // 분할 배낭 문제를 해결하는 함수
    public static double fractionalKnapsack(Item[] items, int capacity) {
        // 항목을 단위 무게당 가치가 높은 순으로 정렬 (내림차순)
        Arrays.sort(items, new Comparator<Item>() {
            @Override
            public int compare(Item a, Item b) {
                double r1 = (double) a.value / a.weight;
                double r2 = (double) b.value / b.weight;
                return Double.compare(r1, r2);
            }
        });

        double totalValue = 0.0;
        int remainingCapacity = capacity;

        // 항목을 순차적으로 선택하면서 배낭에 담기
        for(Item item : items) {
            if(remainingCapacity == 0) break;

            // 항목 전체를 배낭에 담을 수 있으면 담고, 그렇지 않으면 가능한 만큼만 담음
            if(item.weight <= remainingCapacity) {
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                totalValue += item.value * ((double) remainingCapacity / item.weight);
                remainingCapacity = 0;
            }
        }
        
        return totalValue;
        
    }

    public static void main(String[] args) {
        // 예제 데이터
        Item[] items = {
                new Item(60, 10),
                new Item(100, 20),
                new Item(120, 30)
        };

        int capacity = 50;
        double maxValue = fractionalKnapsack(items, capacity);

        // 출력: 240.0
        System.out.println(maxValue);
    }
}

class Item {
    int value;
    int weight;

    public Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
    }
}