그리디 알고리즘

그리디 알고리즘

• 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법

• 가장 이득을 볼 수 있는 조건을 유추하여 최대의 이득을 보기 위한 알고리즘이다.

• 당장 순간의 선택에만 최적의 답을 고르려고 하므로 최적해를 보장해주지 않는다. 보통 최적해를 구하는 알고리즘 보다 빠른 경우가 많아서 그리디 알고리즘이 효율적인 상황이 많은 것이다.

관련 문제

그리디 알고리즘의 대표적인 예시로는 거스름돈 예제가 있다.

• 당신은 음식점에서 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전을 무한히 가지고 있다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
  위 문제에 아래의 문장을 추가하면, 왜 탐욕법 이라고 불리는지 이해하기 쉬울 것이다.

• 모든 동전의 가격이 하나당 10억원이라서, 당신은 최소한의 동전만을 주고 최대한 많은 동전을 소유하고자 한다.

• 해당 문제는 최대한 큰 단위의 동전을 많이 줘야 한다 라는 간단한 법칙만 발견한다면 쉽게 풀 수 있다.

function solution(value) {
	const coins = [500, 100, 50, 10]; // 동전이 여러개라면 내림차순 정렬 상태여야 한다.
  	let count = 0;
  
  	for(let i = 0; i < coins.length; i++) {
      		const coin = coins[i];
      
    		count += Math.floor(value / coin);
      		value = value % coin;
    	}
  
  	return count;
}