javascript - 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 하는 방식으로 문제를 해결하는 방법론입니다. 이 알고리즘이 항상 최적의 해를 구하는 것은 아니지만, 특정 문제들에 대해서는 빠르게 근사적인 해답을 찾을 수 있습니다.

예시로 많이 사용되는 거스름돈 문제를 살펴봅시다.

문제: 손님에게 N원을 거슬러주어야 할 때, 가지고 있는 동전의 종류는 500원, 100원, 50원, 10원이며, 손님에게 동전의 개수를 최소로 하여 N원을 거슬러 주어야한다. 동전의 개수를 구하시오.

 

1. 일반적인 방법

주어진 동전들을 어떤 방식으로든 조합하여 N원을 만들 수 있습니다. 하지만, 그렇게 하면 경우의 수가 많아져서 계산이 오래 걸릴 수 있습니다.

2. 그리디 알고리즘 활용

function change(n) {
let coins = [500, 100, 50, 10];
let count = 0;

for (let coin of coins) {
    count += Math.floor(n / coin); // 현재 동전으로 거슬러 줄 수 있는 개수를 더한다.
    n %= coin; // 남은 거스름돈 업데이트
}

return count;
}

이 방법은 동전의 큰 단위부터 최대한 거슬러 주는 방식으로, 동전의 개수를 최소화하게 됩니다.

그리디 알고리즘의 핵심은 각 단계에서 최선의 선택만을 따르게 되며, 이러한 선택이 전체에서도 최선이라는 보장은 없습니다. 하지만 거스름돈 문제와 같이 그리디 알고리즘의 특성에 적합한 문제에서는 효과적으로 해답을 찾을 수 있습니다.

 

3. 그리디 알고리즘 일반 형태

function greedy() {
1. 해결해야 할 문제의 데이터를 정렬 또는 선택의 기준 설정
2. 가장 최선의 선택을 반복적으로 수행
}

• 문제 파악하기
• 선택의 기준이나 순서 파악하기
• 선택의 기준에 따라 해결 방법 구현하기

이처럼 그리디 알고리즘은 현재 상황에서 최선의 선택을 반복적으로 수행하여 문제의 해답에 접근하는 방법입니다.