그리디 알고리즘 (Greedy Algorithm)

특징

• 매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법
  • 빠르게 근사치를 계산
  • 결과적으로는 최적해가 아닐 수 있다

예시

1) Activity Selection Problem

• N 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기
  
  1) 종료 시간 기준으로 정렬
  2) 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택
  

---

2) 거스름돈 (동전의 개수 가장 적게)

• Case 1) 잔돈: 890, 동전 종류: 10, 50, 100, 500
  -> 큰 동전부터 계산
  
  그리디 알고리즘의 조건을 따질 때 A가 B로 이루어져 있는지 아닌지를 따진다.
  위의 상황을 예로 들면, 서로 앞에 더 큰 동전을 구성할 수 있는 동전들로 하위 구조를 이루고 있기 때문에 그리디 알고리즘이 적용 가능하다.

---

• Case 2) 잔돈: 890, 동전 종류: 10, 50, 100, 400, 500
  -> 큰 동전부터 계산
  
  그리디 알고리즘의 결과는 9개인데, 최적 해는 7개이다.
  위의 동전 구성을 보면 400원을 조합한다고 500원을 만들 수 없다. 즉 500원 개수 선택에 따라 400원의 개수가 완전히 달라질 수 있기 때문에 그리디 알고리즘을 적용할 수 없다.

그리디 알고리즘 적용 조건

• 그리디 알고리즘은 빠르지만 최적해를 보장하지는 못한다
• 따라서 아래의 두 조건에 해당하는 경우에만 적용 가능하다

1. 탐욕적 선택 특성 (Greedy choice property)
   • 지금 선택이 다음 선택에 영향을 주지 않음
     = 현재 값에 따라서 그 다음 값이 구성이 되는지 안되는지, 서로 영향이 있는지 없는지
2. 최적 부분 구조 (Optimal substructure)
   • 전체 문제의 최적해는 부분 문제의 최적해로 이루어진다

소스코드

1) 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) {
        // Test code
        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);
    }
}

2) 거스름돈 (동전의 개수 가장 적게)

// 거스름돈 문제

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

public class Main2 {
    // receviedMoney: 지불받은 돈, 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++) {
            // 동전 단위가 잔돈보다 크면 continue
            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) {
        // Test code
        getChangeCoins(1000, 100);
        getChangeCoins(1234, 500);
    }
}