Greedy[그리디]

  그리디 알고리즘은 '탐욕법'이라고도 하는데, 탐욕적으로 문제를 푸는 알고리즘이다. 핵심은 '현재 상황에서 지금 당장 좋은 것만 선택하는 방법' 이다. 그리디 알고리즘을 이용하면 ❗️매 순간 가장 좋아보이는 것을 선택하며 나중에 미칠 영향에 대해서는 고려하지 않는다. 보통 코딩테스트 유형을 보면 정형화 되어있는 문제들이 있는데, 그리디 알고리즘은 그렇지 않다. 사전에 외우지 않고 알고리즘 사고 능력을 통해 풀어야 하는 문제들이 출제된다. 즉, 문제의 유형이 매우 다양하기 떄문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다.

 

  결국에는 많은 문제를 풀어보면서 훈련해야한다. 만약 회사 코딩테스트에서 문제로 그리디 알고리즘 문제를 출제했다면 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 있는가를 판단하기 위해서라고 생각하면 된다. 그리디 알고리즘의 가장 대표적인 예가 '거스름돈' 이다. 

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

5585번: 거스름돈

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

# 거슬러 줘야하는 금액
n = 1000 - int(input())

# 동전의 화폐 단위
coin_types = [500, 100, 50, 10, 5, 1]

# 화폐 단위 하나씩 돌면서 잔돈의 개수 구하기
count = 0
for i in coin_types:
    count += n // i
    n %= i
print(count)

언제나 거스름돈 개수가 가장 적게 잔돌을 주기 위해서는 화폐단위가 가장 큰 금액부터 주면된다.