[알고리즘] # 1. 그리디 알고리즘 (Greedy Algorithm) 이론과 예제 풀이

 

풀이에 사용한 언어 : C언어

그리디 알고리즘
- 현재 주어진 Step만을 기준으로 하여, 최적의 해를 구하는 알고리즘이다.
다만, 매 Step마다 최적의 해를 구했다해도 최종 결과는 최적의 해가 아닐 수 있다. 그래서 불완전한 알고리즘이며 특수한 경우에만 그리디 알고리즘을 쓴다.

대표적인 예제가 거스름돈이다. 우리가 맥도날드에서 상하이스파이시버거세트를 산다하자. 한 때, 굉장히 좋아했는데 이사한 집 근처에 맥날이 없어서 가격이 기억안나지만 대충 5500원이였던 것 같다.
10000원을 지불하고 4500원을 거슬러 받는다 하면, 일반적으로 1000원 4장, 500원 1개로 총 5번의 거스름을 받는게 맞다. 화폐는 그 단위가 5000,1000,500,100... 이런 식으로 정해져 있고 내림차순 (혹은 오름차순)이기 때문에 그리디를 적용해도 괜찮다.

아래 코드 내용은, 돈을 입력받았을 때, (예를 들면 3100원이라 하자) 500원,100원,50원,10원만 갖고 있을 때 가장 최소한으로 거스름을 한 결과를 구현하고자 했다.

물론 아래 코드는 실행해보면 잘못되었음을 알 수 있다.

#include <stdio.h>

int main()
{
	int money;
	scanf("%d",&money);
	int n,m,k,l=0;
	
	while(money>0)
	{
		money = money%500;
		n = money/500;
		
		if (money<500)
		{
			money = money%100;
			m = money/100;
			if (money<100)
			{
				money = money%50;
				k = money/50;
				if (money<50)
				{
					money = money%10;
					l = money/10;
				}
			}
		}
		printf("%d",n+m+k+l);
		
	}
	
	return 0;
}

그럼 왜 틀렸는지 분석을 해봤는데, 단순히 코드의 순서가 잘못되었다고 판단 중이다.
보면 %연산자를 먼저한 값을 money에 집어넣고 그 다음 몫연산자를 카운팅했으니 값이 이상하게 나올 수 밖에 없다.
또한, if문은 필요가 없다. 반복을 수행하면서 알아서 500원 이하면 100으로 넘어갈테니까.

#include <stdio.h>

int main()
{
	int cnt = 0;
	int money;
	scanf("%d",&money);
	
	while (money>0)
	{
		cnt += money/500;
		money = money%500;
		
		cnt += money/100;
		money = money%100;
		
		cnt += money/50;
		money = money%50;
		
		cnt += money/10;
		money = money/10;
	}
	
	printf("%d",cnt);
	
	return 0;
}

그래서 재구성해본 결과는 이러하다.

잘 나온다. 4700원을 먼저 500원으로 거스르면 9번이고 나머지 200원은 100원으로 거스르면 2번이니까 총합 11번이다.
결과는 같다.