그리디(Greedy)

자바에서의 그리디(Greedy) 알고리즘은 최적해를 찾는 문제를 해결하기 위한 한 가지 접근 방법이다. 
그리디 알고리즘은 각 단계에서 가장 최선의 선택을 하여 전체 문제의 최적해를 찾아내는 방식으로 작동한다.

그리디 알고리즘의 일반적인 구현 단계

• 문제 이해 및 모델링: 문제를 잘 이해하고, 최적해를 찾기 위한 그리디 전략을 정의한다.
• 탐욕 선택 기준 정의: 각 단계에서 가장 좋은 선택을 어떤 기준으로 판단할 것인지 정의한다. 이 선택 기준은 문제의 특성에 따라 다를 수 있다.
• 탐욕적 선택 수행: 정의한 선택 기준에 따라 각 단계에서 최선의 선택을 수행한다.
• 유효성 검사 및 해 검증: 선택한 해가 문제의 조건을 만족하는지 검사하고, 전체 해가 올바른지 검증한다.
  
  

밑 예제는 거스름돈을 줄 때 가장 적은 동전 개수로 거슬러 주는 문제를 예로 들어보겠다.

예제) 거스름돈

 

public class GreedyExample {
    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10};
        int amount = 1260;
        int count = 0;

        for (int i = 0; i < coins.length; i++) {
            int coinCount = amount / coins[i]; // 현재 동전 단위로 거슬러 줄 수 있는 개수
            count += coinCount; // 동전 개수 누적
            amount -= coinCount * coins[i]; // 사용한 동전만큼 거스름돈에서 빼기
        }

        System.out.println("Minimum number of coins: " + count);
    }
}

위 코드는 그리디 알고리즘을 사용하여 거스름돈을 최소한의 동전 개수로 계산하는 예제이다.

각 단계에서 가장 큰 동전부터 선택하여 거스름돈을 계산하고, 선택한 동전의 개수를 누적한다.

 

알고리즘의 대표적인 문제

• 거스름돈 문제(Change-making Problem)
  가장 대표적인 그리디 알고리즘 예시로, 가장 큰 단위의 동전부터 사용하여 최소한의 동전 개수로 거스름돈을 만드는 문제이다.
• 부분 배낭 문제(Fractional Knapsack Problem)
  주어진 가방의 용량에 최대한 가치가 높은 물건을 넣는 문제로, 물건을 일부 분할하여 넣을 수 있을 때 그리디 알고리즘이 사용된다.
• 활동 선택 문제(Activity Selection Problem)
  여러 활동들 사이에서 시간이 겹치지 않게 최대한 많은 활동을 선택하는 문제이다. 종료 시간이 빠른 활동을 우선적으로 선택하는 그리디 전략이 적용된다.
• 탐욕적 스케줄링 문제(Greedy Scheduling Problem)
  일정 시간 내에 가장 많은 작업을 처리하는 문제에서도 그리디 알고리즘이 사용될 수 있다.
• 다익스트라 최단 경로 알고리즘
  그래프에서 출발점으로부터 각 정점까지의 최단 경로를 구하는 알고리즘으로, 그리디 알고리즘의 한 예이다.
• 크루스칼 최소 신장 트리 알고리즘
  그래프에서 모든 정점을 포함하는 트리를 만들기 위해 가장 작은 가중치의 간선을 선택하는 알고리즘으로, 그리디 알고리즘의 한 예이다.
• 허프만 코딩(Huffman Coding)
  데이터 압축을 위한 트리 기반 알고리즘으로, 빈도가 높은 문자에 더 짧은 코드를 할당하여 효율적인 압축을 달성하는 그리디 알고리즘의 한 예이다.
• 최대 수입 스케줄링 문제(Maximum Revenue Scheduling Problem)
  각 작업마다 수익과 완료 시간이 주어질 때, 최대 수입을 얻을 수 있는 작업 스케줄을 선택하는 문제이다.