그리디

김동한·2024년 7월 19일

CODE_TEST

목록 보기

2/39

그리디(greedy) 알고리즘

greedy는 '탐욕스러운' 이라는 뜻을 가지고 있다. 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 선택지를 고르는 탐욕적인 방법을 의미한다. 해당 선택이 나중에 끼칠 영향 따위는 생각하지 않는다. 반대로 생각하면, 문제가 주어졌을 때 해당 문제가 단순히 현재 상황에서 좋은 것만 고르는 것으로 선택해도 되는지 파악할 수 있어야 한다. 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출 할 수 있다.

그리디 알고리즘으로 문제를 해결하기 위해서는 아래의 조건을 만족해야한다.

탐욕적 선택 속성 (Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조 (Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

대표적인 그리디 알고리즘 문제를 통해서 확인해보자.

거스름돈 문제

(문제 사진 클릭시 해당 백준 링크로 이동 가능)

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예제 입출력 1

# 입력
380

# 출력
4

예제 입출력 2

# 입력
1

# 출력
15

정답 코드

price=int(input())

change=1000-price
coin_cnt=0

# 500,100,50,10,1
coin_list=[500,100,50,10,5,1]
for coin in coin_list:
    coin_cnt+=change//coin
    # print("coin",coin)
    # print("current_coint_cnt",coin_cnt)
    change%=coin
    # print("current_change",change)


print(coin_cnt)

해당 문제는 거스름돈을 동전으로 받을 때, 어떻게 해야 제일 적은 양의 동전으로 거스름돈을 받을 수 있는지를 구해야하는 문제이다. 먼저 거스름돈은 500엔부터 차례로 500,100,50,10,5,1엔으로 합쳐 거스름돈을 계산할 수 있다. 여기서, 각 동전의 갯수는 무수히 많다.

거스름돈을 가격이 높은 동전부터 차례로 계산한다면, 동전의 갯수를 최소화 할 수 있다. 예를들어, 예제 입력 1에서는 620 (1000-380)엔 만큼의 거스름돈을 받아야한다. 620엔을 적은 양의 동전으로 만드려면, 가지고 있는 동전 중 금액이 가장 높은 것부터 차례대로 구성하면 된다.

먼저 500엔으로 620엔을 나누면, 120엔이 남고, 1개의 500엔 동전이 된다. 그 후, 남은 120엔을 또 다음으로 높은 가격의 동전인 100엔으로 나누면, 20엔이 남는다. 20엔은 그 다음 가격인 50엔으로 나눌 수 없기 때문에 넘어가고, 10엔 2개로 구할 수 있으니, 총 500엔 1개 100엔 2개 10엔 2개로 동전의 갯수를 최소화해 거스름돈을 줄 수 있다.

거스름돈 문제에서 부분적인 해는, 현재 남은 잔돈을 어떻게 해야 가장 적은 동전의 갯수로 계산하냐이다. 잔돈이 620엔일 때는, 500엔으로 계산해야 가장적고, 그 이후 120엔일때는 100엔으로 계산해야 가장 적으며, 마지막 남은 20엔일 때는 10엔으로 계산해야 가장 적다. 각각의 현재 잔돈 상태에서 적은 동전의 갯수를 고르면 그 합이 최종적인 해가 된다.

또한, 앞에서 500엔으로 먼저 잔액을 계산했다고해서 이후에 100엔을 못선택하거나 하는 것도 아니다. 현재 잔돈에 맞춰서만 동전의 갯수를 정하면 되니 앞서 언급한 그리디 알고리즘의 두 조건을 모두 만족하는 문제임을 알 수 있다.

이 문제는 큰 단위의 화폐가 작은 단위의 배수이기 때문에 그리디 알고리즘으로 해결 가능했다. 화폐의 단위가 무작위로 주어지면 다이나믹 프로그래밍으로 해결 가능하다.

대부분의 그리디 알고리즘 문제는 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 정당한지 검토할 수 있어야 답을 도출할 수 있다.