[Algorithm] 탐욕법(Greedy) 알고리즘 개념 및 예제

 

이번 포스팅에선 탐욕법(그리디) 알고리즘에 대해 알아보겠습니다.

개념과 알고리즘을 사용하는 조건을 알아보고, 동전 문제를 통해 활용 예시를 살펴보겠습니다.

* 언어는 C++로 진행됩니다.

 

 

목차

📃 그리디 알고리즘 개념 및 조건

📃 그리디 알고리즘 예제 - 동전 문제

 

 

 

 

그리디 알고리즘 개념 및 조건

 

📌 개념

그리디 알고리즘은 가장 최선의 선택만을 쫒아가는 알고리즘입니다. 다이나믹 프로그래밍의 경우, 다양한 경우들을 하나하나 살펴보면서 최선의 수를 찾고자 했습니다. 그와 달리, 그리디 알고리즘은 오직 눈앞의 최선만을 쫒아 갑니다. 

 

 

 

 

그리디 알고리즘은 Best Solution을 찾기 위한 알고리즘은 아닙니다. 그저 최선을 쫓다보면 결과도 좋겠지 하는 막연한 기대가 구현된 알고리즘이라 할 수 있습니다. 이때문에 현업이나 복잡한 상황에선 쓰이지 않습니다. 간단한 코딩 테스트에서 많이 등장하는 문제입니다. 

 

그럼에도 가장 빠르게 최적에 가까운 근접값을 찾아낸다는 점이 장점입니다.

 

 

 

 

📌 조건

하지만 그리디 알고리즘도 Good Solution을 뽑아내기 위한 알고리즘입니다. 특정 조건에서 사용한다면 그리디 알고리즘은 다이나믹 알고리즘보타 효율적으로 값을 찾아나갈 수 있습니다. 

 

👉 탐욕스로운 선택이 언제나 안전하다.

눈앞의 최선을 쫓는 것이 항상 안전하다는 전제가 필요합니다. 앞의 선택과 뒤의 선택이 서로 관련 없어야 합니다.

 

👉 최적 부분 구조

문제는 여러 단계에 걸쳐 해결됩니다. 이 여러 단계들의 각각이 최적 문제 해결 방법으로 풀려야 합니다. 

 

 

 

 

그리디 알고리즘 예제 - 동전 문제

 

📌 동전 문제: 최소한의 동전만을 사용하라.

당신은 마트의 사장입니다. 만약 손님이 돈을 지불했을 때, 당신은 500원, 100원, 50원, 10원 동전으로 거스름돈을 줍니다. 동전은 무한개 존재합니다. 손님에게 거슬러줘야 하는 돈이 N원일 때, 사용해야 하는 동전의 최소 개수를 구하시오. 단, N은 10의 배수이다.

 

 

탐욕법은 꼭 2가지 조건을 만족해야 함을 잊지 말아야 합니다.

 

 

풀이

(1) 무조건 큰 동전부터 소진합니다.

(2) N이 500 미만이 될 때까지 500씩 빼줍니다.

(3) N이 500 미만이 되었다면, 이제 100 미만이 될 때까지 100씩 빼줍니다.

(4) 이런 방식으로 N이 0이 될 때까지 소진한 후, 이제까지 사용했던 동전 개수를 반환합니다.

 

 

 

📌 코드

 

패키지를 미리 입력하고, 함수 원형을 선언합니다.

#include <iostream>
#include <string.h>
#include <string>
#include <list>
using namespace std;

int solution(int);

 

 

N을 입력받는 코드를 작성합니다.

N을 입력받으면 바로 solution() 함수로 전달하여 최적의 동전 개수를 반환하도록 합니다.

int main(void)
{
	int num;
	cin >> num;
	cout << solution(num) << endl;;
}

 

 

solution() 함수를 정의합니다.

list를 선언함과 동시에 초기화시키고, 반복자를 이요하여 리스트 순회를 하도록 했습니다. for문 안에 while문을 넣어서 조건을 만족(N < 동전크기)할 때까지 반복하도록 했습니다. 

int solution(int N)
{
	int count = 0;
	list<int> money_list = {500, 100, 50, 10};
	for (list<int>::iterator iter=money_list.begin(); iter!=money_list.end(); iter++){
		int a = *iter;
		while (N >= a){
			N = N - a;
			count += 1;
		}
	}
	return count;
}

 

 

 

전체 코드입니다.

#include <iostream>
#include <string.h>
#include <string>
#include <list>
using namespace std;

int solution(int);

int main(void)
{
	int num;
	cin >> num;
	cout << solution(num) << endl;;
}


int solution(int N)
{
	int count = 0;
	list<int> money_list = {500, 100, 50, 10};
	for (list<int>::iterator iter=money_list.begin(); iter!=money_list.end(); iter++){
		int a = *iter;
		while (N >= a){
			N = N - a;
			count += 1;
		}
	}
	return count;
}

 

결과

총 거스름돈은 얼마인가요? 1450
7

500원 2개, 100원 4개, 50원 1개를 이용하여 돈을 거슬러줬습니다.

 

 

 

 

지금까지 탐욕법(그리디) 알고리즘에 대해 알아보았습니다. 언뜻보면 간단해보이지만 문제를 꼬면 꽤 귀찮아질 수 있는 알고리즘입니다. 그러니 문제를 풀어보며 그리디 알고리즘에 익숙해지시길 바랍니다.

 

 

https://www.acmicpc.net/step/33

그리디 알고리즘 단계