프로그래머스보다 백준이 알고리즘에 따른 문제 분류가 잘 되어 있는 것 같아서 제일 낮은 등급부터 알고리즘 문제를 풀어보도록 하자...

📍문제

[BOJ] 5585번: 거스름돈

📍풀이

• 큰 돈을 거스름돈으로 줘야지 가장 적은 개수의 동전이 반환되므로 500엔을 먼저 주는 방식으로 돈 계산을 해야한다.
• coins를 500, 100, 50, 10, 5, 1의 리스트로 정의. 이미 내림차순 정렬이므로 따로 정렬해줄 필요가 없다.

💻나의 코드

money = 1000 - int(input()) # 잔돈
coins = [500, 100, 50, 10, 5, 1] # 거스름돈 리스트
cnt = 0 # 잔돈의 개수 초기화
for coin in coins:
    cnt += money // coin # 잔돈의 개수
    money %= coin # 남은 돈 
print(cnt)

📍그리디 알고리즘 (탐욕법)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법이라 탐욕법이라 불리운다.
• 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 따라서 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• BOJ 5585번문제가 그리디알고리즘 문제인 이유는 가장 적은 개수의 거스름돈을 반환하는 문제인데, 이를 구하기 위한 최소한의 아이디어는 거스름돈의 단위가 가장 큰 돈을 먼저 거스름돈으로 계산해서 주는 것이다.
• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 제시해준다.

그리디알고리즘의 정당성

• 그리디 알고리즘을 이용했을 때 최적의 해를 찾지 못할 가능성이 더 크다. 하지만 위 문제처럼 탐욕적으로 문제를 접근했을 때 정확한 답을 찾을 수 있다면 매우 효과적이고 직관적이다.
• 따라서 단순히 좋아보이는 것으로 반복선택해도 최적의 해를 구할 수 있는지 검토해야한다.