그리디(Greedy) 알고리즘

그리디 알고리즘

그리디 알고리즘이란 탐욕알고리즘 혹은 욕심쟁이 알고리즘이라고도 불리우는데, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.

그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한 ‘특정한 상황’에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있다는 점이다.

그리디 알고리즘의 대표적인 예제는 거스름 돈 문제이다. 우리가 흔히 거스름 돈을 줄 때 가장 적은 양의 화폐를 주는 것이 제일 편하다. 예를 들어 560원을 거슬러 주어야 할 때 10원짜리 56개를 주는 것 보다 500원짜리 1개, 50원짜리 1개, 10원짜리 1개를 주는 것이 더 편하다. 따라서 이런 경우 ‘무조건 더 큰 화폐 단위부터 거슬러 준다.’는 알고리즘만 지키면 최적의 해를 보장할 수 있다.

이러한 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제에 접근한다는 점에서 정렬(Sort)기법이 함께 사용되는 경우가 많다.

다음은 간단하게 돈을 입력받으면 가장 적은 수의 동전으로 바꾸어 주는 문제이다.

예를 들어 1260원을 입력받았다고 하자. 그럼 먼저 가장 큰 단위인 500원짜리 동전으로 거슬러 줄 수 있는 경우를 구하고 이어 100원, 50원, 10원 순으로 거슬러 줄 수 있는 경우를 구하여 출력하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<stdio.h>

int main()
{
	int money, result = 0;
	int temp;

	printf("money : ");
	scanf_s("%d", &money);

	result += money / 500;
	money = money % 500;
	result += money / 100;
	money = money % 100;
	result += money / 50;
	money = money % 50;
	result += money / 10;

	printf("동전의 개수 : %d\n", result);

	return 0;
}

위에서 다루어 본 예시와 같이 그리디 알고리즘이 최적의 해를 보장해 주는 경우도 많으나 아쉽게도 최적의 해를 보장하지 못하는 경우가 더 많다. 그럴 때 다이나믹 프로그래밍 등의 기타 알고리즘을 적용해야 하기도 한다.

다음에 추가로 그리디 알고리즘 예제를 조금 더 풀어보도록 하겠다.

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

• ← Previous Post
• Next Post →