그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm) 설명:

그리디 알고리즘은 매 선택의 시점에서 현재 가장 최적인 해결책을 선택하는 방식으로 문제를 해결하는 알고리즘입니다. 이 알고리즘은 항상 최적의 결과를 보장하지는 않지만, 특정 문제들에서는 효율적이고 정확한 답을 제공할 수 있습니다.

그리디 알고리즘의 기본 원칙:

1. 로컬 최적해 선택: 현재 상황에서 가장 최적의 선택을 합니다.
2. 전역 최적해: 그리디 알고리즘은 매 순간의 최적의 선택이 최종 결과에서도 최적이라는 가정하에 진행됩니다. 그러나 이 가정이 항상 성립하지는 않습니다.

그리디 알고리즘의 대표적인 예시:

1. 거스름돈 문제: 가장 큰 액수의 화폐부터 거슬러 줘서 최소 개수의 화폐를 거슬러 주는 문제.
2. 분할 가능한 배낭 문제: 주어진 무게 제한 내에서 아이템들의 가치를 최대화하는 문제.
3. 최소 신장 트리: 그래프에서 모든 노드를 포함하면서 가중치의 합이 최소가 되는 트리.
4. 활동 선택 문제: 서로 겹치지 않으면서 최대한 많은 활동을 선택하는 문제.
5. 허프만 코딩: 데이터를 압축하여 표현하기 위한 방법으로 빈도수가 높은 문자에는 짧은 코드를, 낮은 문자에는 긴 코드를 부여하는 방식.

장점:

1. 구현이 비교적 간단하다.
2. 문제에 따라서는 최적해를 구할 수 있다.

단점:

1. 항상 최적해를 보장하지 않는다. 때로는 그리디 방식의 해가 최적해가 아닐 수 있다.
2. 문제의 구조와 특성에 따라 그리디 알고리즘이 적용되기 어려울 수 있다.

문제:
당신은 상점의 계산대에서 일하고 있습니다. 고객이 지불한 금액이 주어지고, 당신은 그 고객에게 거스름돈으로 주어진 화폐 단위 중에서 가장 적은 수의 화폐로 거슬러 주어야 합니다. 예를 들어, 거스름돈이 126원이고 화폐 단위가 [100, 50, 10, 5, 1]인 경우에는 100원 1개, 10원 2개, 5원 1개, 1원 1개, 총 5개의 화폐로 거슬러 줄 수 있습니다.

요구 사항:
1. 거스름돈의 액수와 사용 가능한 화폐의 단위가 주어집니다.
2. 거슬러 줄 수 있는 화폐의 최소 개수를 구하세요.

JavaScript로의 구현:

function minimumCoinsForChange(total, coins) {
    coins.sort((a, b) => b - a);  // 화폐 단위를 큰 순서대로 정렬
    let count = 0;

    for (let coin of coins) {
        count += Math.floor(total / coin);  // 해당 화폐로 얼마나 거슬러 줄 수 있는지 계산
        total %= coin;  // 남은 거스름돈 계산
    }

    return count;
}

const total = 126;
const coins = [100, 50, 10, 5, 1];
console.log(minimumCoinsForChange(total, coins));  // 출력: 5

이 예제에서는 가장 큰 화폐 단위부터 시작하여 가능한 한 많은 화폐로 거슬러 주는 그리디 방식을 사용합니다. 이 방법은 주어진 화폐 단위들이 작은 단위의 배수일 경우에 항상 최적의 해를 찾을 수 있습니다.

그리디 알고리즘은 문제의 구조를 잘 파악하고 그리디 방식이 최적의 해를 보장하는지 확인해야 사용할 수 있습니다. 문제에 따라서 그리디 방식이 최적의 해를 찾지 못할 때도 많으므로, 항상 그리디가 최적의 방법론이라고 단정짓기 어렵습니다.