탐욕 알고리즘 (Greedy Algorithms)

탐욕 알고리즘은 최적의 문제를 찾기 위해서 해결하려는 순간마다 항상 최적의 답을 택하는 알고리즘이다. 전체 문제를 고려하지않고 항상 단계별로 최적의 문제만 찾으므로 합이 가장 큰 문제를 찾기위해서는 적합하지 않다.탐욕 알고리즘이 적합하지 않은 문제에서는 동적 프로그래밍이 더 나은 접근 방식일 수 있다.

탐욕 알고리즘을 좀더 확장하여 만들어진 알고리즘이 있는데 다익스트라 알고리즘과 허프만 코딩이 있다.
다익스트라 알고리즘은 그래프에서 노드사이의 최단 경로를 찾는데 사용된다. 방문하지 않은 노드들을 탐색하며 다른 노드까지의 임시 거리를 계산하여 업데이트해 나아가는 방식이다.
가장 흔하고 대표적인 탐욕 알고리즘 문제는 동전문제, 배낭 문제로 항상 최적의 해를 구하는 문제이다.

let testMoney = 6.27;
let bills = {
	hundredDollar: 100.0,
	tenDollar: 10.0,
	fiveDollar: 5.0,
	oneDollar: 1.0,
	quarter: 0.25,
	dime: 0.1,
	nickel: 0.05,
	penny: 0.01
}

let FindingChange = (currency, amount) => {
	let resultBills = {};
	let cashLeftover = amount;

	for (let key in currency)	{
		while (cashLeftover >= currency[key])		{
			if (resultBills[key]) {   
				resultBills[key] += 1;
			}   
			else	{
				resultBills[key] = 1;
			}
			cashLeftover = (cashLeftover - currency[key]).toFixed(2)
		}
	}
	return resultBills;
}

FindingChange(bills, testMoney);