그리디 알고리즘 (Greedy) 완전 정복하기 (백준 11914 거스름돈)

그리디 알고리즘 : 현 상황에서 가장 좋은 것들만 고르는 방법 (탐욕 알고리즘이라고도 불린다.)

 

그리디 알고리즘의 특징

---

1. 매 순간 가장 좋은 (점수가 높은) 것만을 선택하며 현재 선택이 미래에 미칠 영향은 고려하지 않는다. (근시안적 선택)
2. 사전에 알고리즘을 숙지하지 않아도 해결할 수 있는 문제 유형이다.
3. 기준에 따라 좋은 것을 선택하는 알고리즘이기에, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준이 함께 포함되며, 따라서 그리디 알고리즘 문제는 자주 정렬 알고리즘과 함께 출제되는 경향이 있다.
4. 최적의 해를 찾는 것에 기반하여 최적화 문제를 해결하기 위한 알고리즘으로 불린다.

 

주로 그리디 알고리즘 유형의 문제는 창의력, 즉, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

(문제를 보고 매 순간 좋은 것만을 선택하여 해결할 수 있는지 시간 복잡도 등을 고려해야 한다.)

 

어느 코딩테스트 문제를 만났을 때, 유형을 판단하기 어렵다면 그리디 알고리즘을 의심해보고,

탐욕 (현재 상황에서 최적의 상태만을 고르는 방식)으로 문제를 해결할 수 있는지 판단해보자.

 

오랜 시간 고민해도 해결할 수 없다면, 다른 알고리즘을 사용하는 방법을 고려해야 한다.

예제를 통해 함께 알아보도록 하자

 

예제 문제 - 거스름돈

---

문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단 거슬러줘야 할 돈은 항상 10의 배수이다. 입력 첫째 줄에 거스름돈의 액수 n이 주어진다. (n은 1~100,000 사이의 정수) 출력  거스름돈 동전의 최소 개수를 출력한다.

 

문제해설

본 문제는 그리디 알고리즘으로 해결할 수 있는 대표적인 문제 유형이다.

그리디 알고리즘 유형 문제의 특성은 문제를 해결하기 위한 아이디어만 떠올리면 된다. 

위 문제의 경우, 가장 큰 화폐 단위부터 돈을 거슬러주면 된다.

또한 거슬러줘야 할 돈은 항상 10의 배수이며, 10원짜리 동전이 존재하기에 거슬러주지 못하는 경우는 없다.

 

따라서 그저 단위가 가장 큰 화폐부터 차례로 돈을 거슬러줄 수 있을 때까지 거슬러주면 된다.

(주의해야 되는 부분은 후술하겠지만, 만약 높은 액수의 동전이 가장 낮은 동전의 배수 형태가 아니면, 위와 같은 방식의 아이디어는 적용할 수 없다.)

 

문제정답

가장 액수가 높은 동전인 500원 부터 차례대로 고객의 돈을 거슬러 줄 수 있는지 확인한다.

여기서 '//' 연산자는 나눗셈에서의 몫을 구하는 것이며, 이 때 소수점 자리수를 모두 제거한다.

또한, '%' 연산은 나눗셈에서 나머지를 구하는 연산자이다.

 

이를 통해서 사용할 동전의 개수와 남은 금액을 계산할 수 있으며, 순차적으로 액수가 높은 동전부터 계산하면 쉽게 해결할 수 있다.

 

 

def solution(n):
    total_coins = 0
    
    for coin in [500, 100, 50, 10]:
        total_coins += n // coin
        n = n % coin
    
    return total_coins

 

예제 문제는 문제 설명 자체도 직관적이고 해결하기 수월했다.

그렇다면, 실전 문제는 어떠할까?

 

실전 문제 - 거스름돈 - 14914 난이도 실버 5

---

문제 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇개인지 알려주는 프로그램을 작성하라 입력 첫째 줄에 거스름돈의 액수 n이 주어진다. (n은 1~100,000 사이의 정수) 출력  거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

문제해설

본 문제는 그리디 하나로만 해결하기는 어려울 것이다.

예제와는 어떻게 다르기에, 그리디로만 해결하기가 어려워진 것일까?

 

차이점으로 가장 뚜렷한 것은 2원과 5원 짜리로만 거슬러줄 수 있기에, 거슬러줄 수 없는 경우의 수가 추가되었다.

 

돈 단위가 5원과 2원으로 바뀌었고 이로 인해서 더욱 많은 예외 케이스가 발생한다.

예제 코드로는 고려되지 않는 경우의 수가 너무 많기 때문에 예제 문제에서는 고려하지 않았던 부분을 고려해야 한다.

 

예외적인 상황이 발생하는 대표적인 예시로는

13원이 있다.

 

거슬러야 될 금액	사용한 동전 수		거슬러준 금액	남은 금액
	2원	5원
13원	-	2개	10원	3원
3원	1개	-	2원	1원
1원	-	-	-	1원 (거슬러줄 수 없음)

 

가장 큰 동전부터 차례로 거슬러주기 때문에 거슬러주지 못하는 경우가 발생한다.

하지만 위 13원은 아래와 같은 방법으로 거슬러줄 수 있다.

거슬러야 될 금액	사용한 동전 수		거슬러준 금액	남은 금액
	2원	5원
13원	-	1개	5원	8원
8원	4개	-	8원	0원

 

위와 같은 경우엔 총 5개의 동전으로 문제를 해결할 수 있다.

 

두 예제를 보면서 느껴야 할 점은,

그렇다면 각 상황에서의 모든 동전의 개수를 기록해가면서 경우의수를 가려가면 되겠다!

라는 점이다.

 

이러한 방식을 동적계획법(Dynamic Programming, DP)이라고 한다.

한 번 계산한 경우를 기록하여, 나중에 추가 연산 없이 활용하고자 고안된 방법이다.

따라서 모든 케이스를 기록하는 별도의 배열(리스트)를 만들어서

문제를 해결하기 위해 사용하면 된다.

(5원이 1개 사용될 때의 동전의 개수, 2개 사용될 때의 동전의 개수 .... )

 

이는 다음 포스팅에서 정리해보기로 하고, 지금은 간단한 개념만 익힌 상태로 문제를 해결해보자.

 

문제정답

기존에 함수로 문제를 해결해야하는 프로그래머스와 달리, BOJ의 문제이기에, input과 output 출력구분 형식으로 작성했다.

dp와 그리디가 함께 사용되면 아래와 같은 방식으로 문제를 해결할 수 있다.

n = int(input())
dp = [0 for _ in range(n//5 + 1)] # dp의 index는 5원 동전의 개수이다.

for i in range(len(dp)):
    if (n - 5 * i) % 2 != 0: # 거슬러줄 수 없는 경우
        dp[i] = -1
    else: # 거슬러줄 수 있는 경우, 2원 동전의 개수와 5원 동전의 개수를 더해서 저장한다.
        dp[i] = (n - 5 * i) // 2 + i

dp = [c for c in sorted(dp) if c != -1]

if len(dp) == 0:
    print(-1)
else:
    print(dp[0])

 

그리디 풀어볼만한 문제

---

1. 방번호 백준 골드 5

2. 보물 - 백준 실버 4

3. 회의실 배정 - 백준 실버 1