Greedy (그리디 알고리즘)

1. 그리디 알고리즘 (Greedy Algorithm)

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

2. 그리디 알고리즘 예시_1 (1)

• Activity Selection Problem
  • N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기

  

  • 종료 시간 기준으로 정렬
  • 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택

  

3. 그리디 알고리즘 예시_2 (1)

• 거스름돈 (동전의 갯수 가장 적게)
  • 잔돈 : 890
  • 동전 종류 : 10, 50, 100, 500

  ⇒ 큰 동전부터 계산

4. 그리디 알고리즘 적용 조건

• 그리디 알고리즘으 빠르지만 최적해를 보장하지는 못함
• 하기 두 가지 조건에 해당하는 경우 적용 가능

  • 탐욕적 선택 특성 (Greedy choice property)

    ⇒ 지금 선택이 다음 선택에 영향을 주지 않음

  • 최적 부분 구조(Optimal substructure)

    ⇒ 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐

(예시 : 거스름돈)

// 거스름돈 문제

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

public class Main2 {
    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) {
        // Test code
        getChangeCoins(1000, 100);
        getChangeCoins(1234, 500);
    }
}