탐욕 알고리즘

탐욕 알고리즘이라고 하는 녀석을 알아보자.

이녀석은 매 순간순간 최선의 선택을 하는 탐요스러운 녀석이다.

이 알고리즘은 전체를 고려하기 보다 문제를 부분적으로 나누어 나누어진 문제에 대해 최적의 해답을 구한다.

설명은 여기까지하고

대표적으로 거스름돈을 계산하는 문제가 있다.

function coins(c){
    var i=0;
    var coin = [10,5,1];
    var coinCount=new Array();
 
    while(c>0){
        coinCount.push(parseInt(c/coin[i]));
        c=c%coin[i];
        i++;
    }
 
    return coinCount;
}
console.log(coins(26));
console.log(coins(31));
console.log(coins(41));
console.log(coins(1));
console.log(coins(31));

알고리즘 이름이 특이해서 함 알아보았다 ㅋㅋㅋㅋㅋ

이 탐욕 알고리즘은 최단 경로 알고리즘이나, 최소 비용 신장 트리, 배낭 채우기 문제에서 이용하고 있는 알고리즘이다.