[Algorithm] 그리디

오도원공육사·2021년 7월 9일

그리디 알고리즘

알고리즘

목록 보기

13/17

출처. 이것이 코딩테스트다 [나동빈]

당장 좋은 것만 선택하는 그리디

그리디(Greedy) 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 국내에서는 탐욕법이라고도 한다. 이름처럼 단순하게 탐욕적으로 문제를 푸는 알고리즘이다. 그렇다면 탐욕적으로 푼다는 것이 무슨 말일까?

현재 상황에서 지금 당장 좋은 것만 고르는 방법

매 순간 가장 좋은 선택을 하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기위한 최소한의 아이디어를 요구한다. 따라서 현재상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야한다.

특징

그리디 알고리즘은 기준에 따라 가장 좋은 것(적합한 것)을 선택하는 알고리즘이다. 그래서 문제에서 "가장 큰 순서대로", "가장 작은 순서대로"와 같이 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬을 했을 때 만족시킬 수 있으므로 정렬 알고리즘과 자주 짝을 이뤄 출제된다.

예시 - 거스름돈

그리디 알고리즘 문제로 가장 대표적인 거스름돈 문제를 살펴보자.

문제

거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다. 이때 손님에게 거슬러 줘야할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

해설

간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.

"가장 큰 화폐 단위부터" 거슬러 주는 것이다.

처음 N원을 가장 먼저 500원으로 최대한 거슬러 주고, 그 다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 주는 것이다. 그러면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

예시

입력으로 주어진 N이 1260이라면 다음과 같은 과정을 통해 거슬러 줄 수 있다.
- 남은 돈 : 1260원
- 손님 : 0원
  
  step 1) 1260원에서 500원짜리로 거슬러 줄 수 있는 돈 1000원, 즉 500원 2개이고 남은 돈은 260원이다.
- 남은 돈 : 260원
- 손님 : 500원, 500원
  
  step 2) 260원에서 100원 단위로 거슬러 200원을 남기고 60원이 남는다.
- 남은 돈 : 60원
- 손님 : 500원, 500원, 100원, 100원
  
  step 3) 60원에서 50원 단위로 거슬러 주고 10원이 남는다.
- 남은 돈 : 10원
- 손님 : 500원, 500원, 100원, 100원, 50원

소스코드

파이썬

n = int(input())
count = 0

# 큰 단위 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
	n %= coin

print(count)

C언어

#include <stdio.h>

int main() {
	int n, count = 0;
	int coinTypes[4] = {500, 100, 50, 10};
	scanf("%d", &n);
	
	for(int i = 0; i < 4; i++) {
		count += n / coinTypes[i];
		n %= coinTypes[i];
	}
	
	print("%d", count);

	return 0;
}

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분 그리디 알고리즘을 이용했을 때 "최적의 해"를 찾을 수 없는 경우가 많다. 하지만 거스름돈 문제에서 "가장 큰 화폐 단위부터" 거슬러 주는 것과 같이, 탐욕적으로 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

거스름돈 문제를 그리디 알고리즘으로 해결 가능한 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위에 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를 들어 화페단위가 500, 400, 100원이고 거슬러야하는 돈이 800원인 경우를 생각해보자. 이때 그리디 알고리즘은 4개의 동전(500 + 100 + 100 + 100)을 거슬러 줘야한다. 그러나 최적의 해는 2개의 동전(400 + 400)을 거슬러 주는 것이다.

그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야한다.