그리디 알고리즘
그리디 알고리즘
그리디 알고리즘은 "매 선택에서 지금 이순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. Greedy라는 단어는 우리말로 탐욕적인 이라고 해석되기 때문에 탐욕법이라고도 불린다. 가장 이득을 볼 수 있는 조건을 유추하여 최대의 이득을 보기 위한 알고리즘이라고 할 수 있다.
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
그리디 알고리즘 주의점
그리디 알고리즘을 풀 때 주의할 점은, 현재의 상황에 가장 적합한 답을 도출하는 알고리즘이다. 그렇다면 문제를 풀 때 사용한 조건 또는 알고리즘이 가장 적합하다는 것에 대한 확신이 존재해야 한다.
그리디 알고리즘 대표적인 문제(거스름돈)
<문제>
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
[문제 해설]
동전의 최소 개수를 구해야 하는 문제이기 때문에, 가장 큰 화폐 단위부터 돈을 거슬러 주는 것입니다.
거스름 돈이 N원일 때, 500원으로 최대한 많이 거슬러주고, 순서대로 100원, 50원, 10원을 써서 거슬러주면 됩니다.
이제 N이 1,260 일 때의 예시를 확인해봅시다.
[문제 풀이]
[Step 1] 남은 돈: 1,260원
점원에게 1,260원이 있고 이제 손님에게 동전으로 거슬러줘야 합니다.
[Step 2] 남은 돈: 260원
500원 짜리로 거슬러 줄 수 있는 돈은 1,000원입니다. 즉, 500원 2개를 빼면 260원이 남습니다.
[Step 3] 남은 돈: 60원
100원 짜리로 거슬러 줄 수 있는 돈은 200원이었습니다. 이제 60원이 남았습니다.
[Step 4] 남은 돈: 10원
50원 짜리로 1개입니다. 이제 10원만 남았습니다.
[Step 5] 남은 돈: 0원
이제 10원 1개를 써서 거스름돈을 모두 거슬러줬습니다.
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)그리디의 정당성
그리디 알고리즘을 이용했을 때, 최적의 해를 찾을 수 없을 가능성이 더 크다. 하지만 거스름돈 문제에서는 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것처럼 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 경우엔 매우 효과적이고 직관적이다. 그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.
그리디 백준 문제 Github 링크
백준 그리디 관련 문제
