그리디 알고리즘은 각 단계에서 최선의 선택을 하는 방식의 알고리즘입니다. 현재 상황에서 가장 좋아 보이는 선택을 하면서 최종적인 해답에 도달하는 방법입니다.

그리디 알고리즘의 특징

• 탐욕적 선택
  매 순간마다 최선의 선택을 합니다.

• 지역 최적해
  각 단계에서의 최적해가 전체적으로도 최적해일 것이라는 가정을 기반으로 합니다.

• 최적 부분 구조
  부분 문제에 대한 최적해를 이용하여 전체 문제에 대한 최적해를 구할 수 있습니다.

그리디 알고리즘의 예시

• 거스름돈 문제
  최소한의 동전 개수로 거스름돈을 주는 문제.

// 거스름돈 문제

import java.util.HashMap;
import java.util.Map;

public class Main2 {
    /**
     * @param receivedMoney - 받은 돈
     * @param price - 물건 가격
     */
    public static void getChangeCoins(int receivedMoney, int price) {
        final int[] coins = {500, 100, 50, 10, 5, 1}; // 거스름돈 종류
        HashMap<Integer, Integer> result = new HashMap<>();

        int change = receivedMoney - price; // 거스름돈
        int cnt = 0; // 거스름돈 갯수

        for (int i = 0; i < coins.length; i++) {
            if(change < coins[i]){
                continue;
            }

            int q = change / coins[i];
            result.put(coins[i], result.getOrDefault(coins[i], 0) + q);

            change %= coins[i];
            cnt += q;
        }

        System.out.println("거스름돈 동전 개수: " + cnt);
        for (Map.Entry<Integer, Integer> cur : result.entrySet()) {
            System.out.println(cur.getKey() + ": " + cur.getValue());
        }
    }

    public static void main(String[] args) {
        getChangeCoins(1000, 100);
        getChangeCoins(1234, 500);
    }
}

• Activity Selection Problem
  활동과 각 활동에 대한 시작시간과 종료시간이 주어질 때 가장 많이 들을 수 있는 경우를 구하는 문제

// 알고리즘 - 그리디 알고리즘
// Activity Selection Problem

import java.util.ArrayList;
import java.util.Collections;

class Activity {
    String name;
    int start;
    int end;

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

public class Main {
    public static void selectActivity(ArrayList<Activity> list) {
        // 종료시간 기준 오름차순 정렬
        Collections.sort(list, (x1, x2) -> x1.end - x2.end);

        int curTime = 0;
        ArrayList<Activity> result = new ArrayList<>();
        for (Activity item : list) {
            if(curTime <= item.start){
                curTime = item.end;
                result.add(item);
            }
        }

        for (Activity item : result) {
            System.out.print(item.name + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayList<Activity> list = new ArrayList<>();
        list.add(new Activity("A", 1, 5));
        list.add(new Activity("B", 4, 5));
        list.add(new Activity("C", 2, 3));
        list.add(new Activity("D", 4, 7));
        list.add(new Activity("E", 6, 10));
        selectActivity(list);
    }
}

그리디 알고리즘의 한계

• 최적해 보장 문제
  항상 최적의 해를 보장하지는 않습니다.

• 적용 가능성
  모든 문제에 그리디 알고리즘을 적용할 수 있는 것은 아닙니다.

• 문제 종속성
  문제의 특성에 따라 적용 가능성이 달라집니다.

그리디 알고리즘의 시간복잡도

그리디 알고리즘의 시간복잡도는 일반적으로 선형 시간복잡도를 갖습니다. 하지만 문제에 따라 다양한 시간복잡도를 가질 수 있습니다.

결론

그리디 알고리즘은 현재 상황에서의 최적해를 선택하여 최종적인 해답에 도달하는 방식으로 매우 간단하고 직관적입니다. 하지만 항상 최적의 해를 보장하지는 않으며, 각 문제의 특성에 따라 적용 가능성을 고려해야 합니다.