그리디

• 그리디란 현재 가장 최적인 답을 택하는 알고리즘이다.
• 즉 관찰을 통해 탐색 범위를 줄이는 알고리즘
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

그리디 알고리즘의 원리

• 최적 부분 구조 : 부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있는 구조.

• 탐욕적 선택 속성 : 각 단계에서의 최적 선택이 전체 문제에서도 최적이라는 속성.
  -즉 앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조 예시!

서울에서 부산으로 최소거리로 간다고 가정하자.
서울에서 대구가는 선택이 대구에서 부산으로 가는 선택에 의해 결정이 되지는 않는다. // 서울 -> 대구 200km , 대구 -> 부산 80km 를 선택하면 된다.
즉 이 문제의 해결 방법은 부분 문제의 최적 해결 방법으로 연결이 된다.

이상적인 풀이 방법

1. 관찰을 통해 탐색 범위를 줄이는 방법을 생각
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 -> 증명해야 한다
3. 구현해서 문제를 통과한다.

활용할 수 있는 대표적인 문제

거스름돈

• 주어진 동전 종류를 사용하여 특정 금액을 만들기 위한 최소한의 동전 개수를 구하는 문제가 있다고 생각하자.

문제 해결

import java.util.Arrays;

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        // 동전 배열을 내림차순으로 정렬
        Arrays.sort(coins);
        reverse(coins);

        int count = 0;  // 사용된 동전의 개수
        int remainingAmount = amount;  // 남은 금액

        // 가장 큰 단위의 동전부터 사용
        for (int coin : coins) {
            if (remainingAmount >= coin) {
                count += remainingAmount / coin;  // 해당 동전의 개수를 더함
                remainingAmount %= coin;  // 남은 금액 갱신
            }
        }

        // 남은 금액이 0이면 모든 금액을 동전으로 채운 것이므로 count 반환
        // 그렇지 않으면 -1 반환
        return remainingAmount == 0 ? count : -1;
    }

    // 배열을 내림차순으로 정렬하는 유틸리티 메서드
    private static void reverse(int[] array) {
        int left = 0, right = array.length - 1;
        while (left < right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};
        int amount = 63;
        int result = minCoins(coins, amount);
        
        if (result != -1) {
            System.out.println("최소 동전 개수: " + result);
        } else {
            System.out.println("해당 금액을 만들 수 없습니다.");
        }
    }
}

활용 예시

• 결정 트리 학습(Decision Tree Learning)
• 활동 선택 문제(Activity selection problem)
• 최소 신장 트리(Minimum spanning tree)
• 크루스칼 알고리즘
• 다익스트라 알고리즘
• 허프만 코드