1. 그리디(Greedy) 알고리즘

당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘이다.

항상 최적의 결과를 도출하지는 않지만, 최적에 근사한 값을 구할 수 있다.

그리디 알고리즘은 무조건 큰, 무조건 작은, 무조건 짧은, 무조건 긴 경우 등등 극단적으로 문제에 접근하며, 정렬 알고리즘과 함께 사용되기도 한다.

1-1.그리디 알고리즘 문제 - 거스름 돈

1760원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러 주는 방법은?

500원부터 시작해서 3개
100원으로는 2개
50원은 1개
10원은 1개

즉, 큰 화폐부터 시작해서 줄여나가면 된다.

function change(money) {
	let result = 0;
	let coin = [500, 100, 50, 10];

	for (let i = 0; i < coin.length; i++) {
		let number = Math.floor(money / coin[i]);
		result = result + number;
		money = money % coin[i];

		coin[i] = [coin[i], number];
	}

	return [result, coin];
}

console.log(change(1660));

자바스크립트에서 초기값을 정해주지 않으면 NaN이 나올 수 있으므로 주의하도록하자.

위의 코드를 이용하면 500, 100, 50, 10을 차례대로 줄여나가면서

총 몇개의 동전이 필요한지, 어떤 동전이 사용되었는지 파악할 수 있다.

1-2.그리디 알고리즘의 특징

그리디는 미래의 선택은 따져보지 않고 오로지 현재의 이익을 바라보는 알고리즘이다.

최적의 해를 보장하지는 않지만, 그에 근사한 값을 도출할 수 있다.

간단하고 직관적이기 떄문에 굉장히 간단하다.

1-3.그리디 알고리즘의 한계

그리디가 도출해낸 해는 최적의 해가 아닐 수 있다.

단계별로 해가 존재할 때, 현재와 미래의 해를 연결하여 생각하는 것이 아니고 오로지 현재의 가장 크거나, 짧은 것 등등 만 생각하기 때문에 문제에 맞게 잘 고려해서 사용해야한다.