15. 그리디 알고리즘 (동전, 거스름돈 문제)

SMALL

출처: https://tinyurl.com/y36kknwt

---

그리디 알고리즘

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.

이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다.

가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다.

그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다.

그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다.

하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

 

그리디 알고리즘은

• greedy choice property
• optimal substructure

특성을 가지는 문제들을 해결하는데 강점이 있다.

즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

 

그리디 알고리즘은 100% 최적해를 보장해주지 않는다.

다만, 어느정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을때에는 사용할 수 있다.

특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기때문에 실용적으로 사용이 가능하다.

허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다.

또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.

https://tinyurl.com/y59gsqnq

---

그리디 알고리즘 사용 예시

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)
• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 최소 신장 트리 (Minimum spanning tree)
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘
• 하프만 코딩
• 크러스컬 알고리즘

---

거스름돈 문제

동전들에 배수관계가 성립할때만 한정.

대부분의 화폐는 1,5,10,25,50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.

 

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

백준 사이트 5585번 문제 거스름돈 파이썬 코드

코드 1 (용량 초과)

#greedy algorithm의 대표적인 예시인 거스름돈의 동전 최소 개수 카운팅
#얼마짜리 물건인지 입력받기
#a엔
a = input()
a = int(a)

#코인의 개수를 세는 역할을 하는 함수를 정의
def countcoin(a):
  cnt500 = 0
  cnt100 = 0
  cnt50 = 0
  cnt10 = 0
  cnt5 = 0
  cnt1 = 0
  #500엔, 100엔, 50엔, 10엔, 5엔, 1엔의 돈이 있으므로 각각을 0으로 초기화
  residu = 1000-a
  #나머지 돈이 얼마인지를 residu 변수에 저장하고, 1000엔을 냈으므로 초기 나머지돈은 1000-a엔
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print
  cnt500 += int(residu/500)
  residu = residu - cnt500*500
  #500엔짜리 동전을 받을 수 있는지, 있다면 그 개수는 몇 개인지를 나눗셈으로 세기
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print
  cnt100 += int(residu/100)
  residu = residu - cnt100*100
  #100엔짜리 동전을 받을 수 있는지, 있다면 그 개수는 몇 개인지를 나눗셈으로 세기
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print
  cnt50 += int(residu/50)
  residu = residu - cnt50*50
  #50엔짜리 동전을 받을 수 있는지, 있다면 그 개수는 몇 개인지를 나눗셈으로 세기
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print
  cnt10 += int(residu/10)
  residu = residu - cnt10*10
  #10엔짜리 동전을 받을 수 있는지, 있다면 그 개수는 몇 개인지를 나눗셈으로 세기
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print
  cnt5 += int(residu/5)
  residu = residu - cnt5*5
  #5엔짜리 동전을 받을 수 있는지, 있다면 그 개수는 몇 개인지를 나눗셈으로 세기
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print
  cnt1 += int(residu/1)
  residu = residu - cnt1*1
  #1엔짜리 동전을 받을 수 있는지, 있다면 그 개수는 몇 개인지를 나눗셈으로 세기
  print(residu)
  #중간과정 결과를 보기 위해 넣은 print

  cnt = cnt500 + cnt100 + cnt50 + cnt10 + cnt5 + cnt1
  #거스름돈의 최소 동전의 개수합을 더하기

  return cnt
  #거스름돈의 최소 동전의 개수를 함수의 출력으로 return하기

print(countcoin(a))
#return된 결과값을 print하기

코드 2 (성공)

#얼마짜리 물건을 사는지 입력받기(a변수에)
a = input()
a = int(a)

#누적 동전 개수
JPY_CoinList = (500,100,50,10,5,1)

#개수를 세주는 함수
def minimum_Coin(value, JPY_CoinList):
#입력을 얼마짜리 물건인지와 동전의 종류가 뭐뭐 있는지를 받는다
  count = 0
  #동전의 개수를 0으로 초기화
  residue = 1000-value
  #거스름돈이 얼마인지 계산(1000엔을 내는 것으로 고정되어 있으니까)
  for i in JPY_CoinList:
    #i가 첫번째면 500, i가 두번째면 100, i가 세번째면 50 등의 순서로 진행하면서 index를 준다
    count += int(residue/i)
    #예를 들어, i가 첫번째인 경우 500원짜리 동전이 몇 개까지 커버가능한지를 센다
    residue -= int(residue/i)*i
    #동전을 센 금액만큼 빼주고 다시 for 루프가 반복될 수 있도록 한다
  return count
  #동전 개수를 몇개인지 return한다

print(minimum_Coin(a, JPY_CoinList))
#함수의 결과를 출력한다

---

코드1 결과

코드 1 결과

코드 2 결과

코드 2 결과

---

백준 사이트 11047번 문제 코드

코드 1 (파이썬)

N, K = input().split()

N = int(N)
K = int(K)

lst = []
for i in range(N):
  a = int(input())
  lst.append(a)

count = []
for i in range(N):
  count.append(0)

def countCoin(N, K, lst, count):
  lst.reverse()
  for i in range(N):
    count[i] += int(K/lst[i])
    K -= count[i]*lst[i]
    print(count[i])
    print(K)
  return count

ans = countCoin(N, K, lst, count)

result = 0
for i in range(len(ans)):
  result += ans[i]

print(result)

코드 2 C언어

#include <stdio.h>
 
int main()
{
    int n, money;
    int i;
    int arr[9];
    int cnt = 0;
 
    scanf("%d,%d", &n, &money);
 
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
 
    for (i = n - 1; i >= 0; i—)
    {
        if (money - arr[i] >= 0)
        {
            money = money - arr[i];
            cnt++;
            i++;
        }
        
    }
 
    printf("%d", cnt);
    return 0;
}

---

코드 1 결과 (파이썬)

코드 1 결과

코드 2 결과 (C언어)

코드 2 결과