Greedy Algorithm으로 문제 해결하기

문제 해결 단계

1. 선택 절차: 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

탐욕 알고리즘의 특징

• 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
• 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
• 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.

탐욕 알고리즘 유형 - 거스름돈

타로는 자주 JOI 잡화접에서 물건을 산다. JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI 잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

// input: 타로가 지불해야하는 금액
// output: 거슬러 받아야하는 잔돈의 최소 동전 개수

function keepTheChange(input){
	//거슬러줘야하는 거스름돈을 선언
  	let change = 1000 - input
    //동전의 수를 카운트하기 위해 count를 선언
	let count = 0;
  	//입력값에 잔돈의 종류가 없기때문에 배열로 선언
  	const coin = [500, 100, 50, 10, 5, 1] 
	//거스름돈 개수가 가장 적게 잔돈을 주어야만 하기 때문에, 가장 금액이 큰 잔돈부터 계산을 시작하기 위해 배열 선언시 내림차순으로 선언
	
    for(let i = 0; i < coin.length; i++){
    	if(change === 0) break; //거스름돈이 0이되는 순간 for문을 멈춤
      count += Math.floor(change/coin[i]); //거스름돈과 잔돈을 나눈 몫을 카운팅
      change %= Math.floor(coin[i]); //거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
    }
  return count
}

greedy Algorithm은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이라고 학습했습니다. 따라서 해당 로직은 “거스름돈을 가장 큰 잔돈부터 나눠서 0원으로 만든다" 라는 최적의 상황을 쫓게 되는 것입니다.