그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는데 사용되는 알고리즘 중 하나로, 각 단계에서 가장 최적인 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다.

그리디 알고리즘은 매 순간 가장 최적인 선택을 하는 것이지만, 이는 전체적으로 최적해를 보장하지는 않습니다.

그리디 알고리즘의 작동 방식은 다음과 같습니다

  1. 문제 해결 방식 정의: 주어진 문제에 대해 그리디 알고리즘을 사용하여 어떤 방식으로 문제를 해결할 것인지 정의합니다.
  2. 선택 단계: 각 단계에서 가능한 선택지 중에서 가장 최적인 선택을 합니다. 이 선택은 현재 단계에서는 최적이지만, 전체적으로 최적이라는 보장은 없습니다.
  3. 실행 및 해결: 선택한 단계에서의 최적 선택을 실행하고, 문제를 부분적으로 해결합니다. 이를 반복하여 전체 문제를 해결합니다.
  4. 최적해 확인: 알고리즘이 종료된 후에 얻은 해를 확인하고, 이것이 최적해인지 검증합니다. 그리디 알고리즘은 보통 근사 알고리즘으로 사용되며, 최적해를 찾는 것을 보장하지 않을 수 있습니다.

그리디 알고리즘은 단순하고 직관적인 접근 방식을 가지고 있어 구현이 비교적 간단하며 빠른 실행 속도를 가질 수 있습니다. 하지만, 항상 최적해를 보장하지는 않습니다.

대표적인 그리디 예시 코드 - 거스름돈 문제

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GreedyChange {
    public static void getChangeCoin(int receivedMoney, int price) {
        final int[] coins = {500, 100, 50, 10, 5, 1};
        HashMap<Integer, Integer> res = 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];
            res.put(coins[i], res.getOrDefault(coins[i],0) + q);

            change %= coins[i];
            cnt += q;
        }
        System.out.println("거스름든 동전 갯수" + cnt);
        for (Map.Entry<Integer, Integer> cur : res.entrySet()) {
            System.out.println(cur.getKey() + " " + cur.getValue());
        }
    }
    public static void main(String[] args) {
	    getChangeCoin(1000, 100);
	    getChangeCoin(1234, 500);
    }
}

그리디 문제에서는 항상 최적해를 구할때 중요한 부분이있다.

위 문제에서는 동전들인데, 보면은 각 동전들이 작은 동전들로 나누어진다. 이 이야기는 결국 직관적으로 고른 최적해가, 그 다음 선택지에 영향을 안끼치게 되는데 이게 그리디를 쓸 때 가장 중요한 조건이다. 결국 욕심쟁이 선택인 부분.

그리디