1. 그리디 알고리즘(탐욕 알고리즘)
전체 문제가 여러 단계로 구성되어 있는 경우에 각 단계별로 최적 해를 구함으로써 전체 문제를 해결하려는 알고리즘 설계 방법.
그리디 알고리즘은 전체적으로 최적인 해가 아니라, 각 단계에서 최적인 해를 찾아가는 근사적인 알고리즘이다. 지역적으로는 최선이지만 전역적으로 최적이라는 보장은 없으므로, 그리디 알고리즘을 적용시킬 수 있는 문제는 지역적으로 최적이면서도 전역적으로 최적이어야 한다.
위의 그림처럼, 그리디 알고리즘의 해가 반드시 전역적으로 최적의 해가 아님을 알 수 있다.
대표적인 그리디 알고리즘의 예시로, 물건을 계산할 때 거스름돈으로 동전 갯수를 최소한으로 거슬러주어야 하는 경우가 있다. 동전의 단위가 모두 배수 형태기 때문이다. 따라서 가장 큰 화폐단위부터 거슬러주면 된다.
결과적으로 그리디 알고리즘을 사용하는 문제는 두 가지 조건을 충족한다.
1. 탐욕스런 선택 조건(greedy choice property)
탐욕적인 선택이 항상 안전하다는 것이 보장된다는 의미이다. 즉, 그리디한 선택이 언제나 최적해를 보장해야한다.
2. 최적 부분 구조 조건(optimal substructure)
문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다. 즉, 전체 문제가 여러 부분 문제로 분할되며 단계마다 최적해가 도출되어야 한다.
위의 예시처럼, 서울에서 부산까지의 최단 경로를 구할 때, 서울에서 대전까지 최단 경로와 대전에서 부산까지 최단 경로가 모여 최적해를 이루는 것을 알 수 있다.
2. 구현
위에 언급한 예시인 거스름돈 문제를 그리디 알고리즘을 사용해 구현해보고자 한다.
문제
거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한히 있다고 가정해보자. 손님에게 거슬러주어야 할 돈이 N원일 때, 거슬러 주어야 할 동전의 최소 개수를 구해본다. 단, N은 항상 10의 배수로 상정한다.
해결
동전의 단위가 모두 배수의 형태이기 때문에 작은 단위 동전들을 종합해 다른 해가 나올 수 없다. 100원, 50원, 10원이 각각 그보다 큰 단위의 동전의 약수가 되기 때문에 작은 동전의 모음은 큰 동전으로 대체된다는 이야기다.
그러므로 최적의 해를 빠르게 구하기 위해선 가장 큰 화폐인 500원부터 차례로 최대 갯수로 거슬러주면 된다.
function greedy(N){
const coin = [500, 100, 50, 10];
let tmp = N;
return coin.reduce((sum, coin) => {
sum += Math.floor(tmp/coin);
tmp -= coin*Math.floor(tmp/coin);
return sum;
}, 0);
}
console.log(greedy(1260)); //500원 2개, 100원 2개, 50원 1개, 10원 1개 => 6개
console.log(greedy(2310)); //500원 4개, 100원 3개, 50원 0개, 10원 1개 => 8개
출처
https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://yganalyst.github.io/concept/algo_cc_book_1/
