본문 바로가기

알고리즘 공부

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

출처: 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번: 거스름돈

문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할

www.acmicpc.net

 

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

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net


백준 사이트 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 결과

'알고리즘 공부' 카테고리의 다른 글

17. 프림 알고리즘  (0) 2019.10.05
16. 크루스칼 알고리즘  (0) 2019.10.04
14. 다익스트라 알고리즘  (0) 2019.10.03
13. 카운팅 정렬(A.K.A 계수 정렬)  (0) 2019.09.29
12. 기수 정렬 (A.K.A Radix sort)  (0) 2019.09.29