그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 매 선택에서 당장 눈 앞에 보이는 최적인 답을 선택하도록 하는 알고리즘이다.

 

대표적인 예제로는 거스름 돈 문제가 있다. 예를들어, 거스름 돈 1260원을 내주어야할 때 10원짜리 동전을 126개 내어주는 

 

것보다는 500원짜리 동전 2개, 100원짜리 동전 2개, 50원짜리 동전 1개, 10원짜리 동전 1개로 총 6개의 동전을 내어주는 것이

 

더욱 편리하다. 그러므로 그리디 알고리즘은 무조건 큰 경우 혹은 무조건 작은 경우대로 문제에 접근하여 수행된다.

 

[예제]

#include <stdio.h>

int main() {
	int input, result = 0;
	scanf("%d", &input);
	result += input / 500;
	input %= 500;
	result += input / 100;
	input %= 100;
	result += input / 50;
	input %= 50;
	result += input / 10;
	printf("%d개의 화폐로 계산할 수 있습니다.", result);
}

 

예를 들어 1260원을 입력하였을 때 몇 개의 화폐로 편리하게 계산할 수 있는지 구하는 코드는 위와 같다.

 

변수 result 에 먼저 500을 나눈 몫을 저장한 다음 100을 나눈 몫을 누적시키고, 50을 나눈 몫을 누적시키고 마지막으로

 

10을 나눈 몫을 누적시키면 된다.

 

즉, 1260원을 입력한다면,

 

(1) 1260에서 500을 나눈 몫은 2 이고 나머지 값은 260이다. 

 

(2) 260에서 100을 나눈 몫은 2 이고 나머지 값은 60이다.

 

(3) 60에서 50을 나눈 몫은 1 이고 나머지 값은 10이다.

 

(4) 10에서 10을 나눈 몫은 1이고 나머지 값은 0이다.

 

  => 그러므로 총 몫을 누적해나가면 2 + 2 + 1 + 1 = 6 이라는 결과를 얻을 수 있다.

 

[결과]

그리디 알고리즘(Greedy Algorithm)

 

---

출처

https://blog.naver.com/ndb796/221242106787

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