📗 그리디 알고리즘이란? 📗
- 그리디 알고리즘이란 어떤한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재상황에서 지금 당장 좋은것만 고르는 방법'을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
- 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 이는 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지를 파악해야한다.
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘 이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. 대체로 이러한 기준은 정렬 알고리즘과 짝을 이뤄 출제 될때 제시해준다.
🎈 그리디 문제 예시
📍 거스름돈 📍
📌문제
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈을 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존대한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
📌 문제해설
이 문제에서 가장 먼저 떠올려야 할 아이디어는 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. 그러면 최소의 동전 개수로 모두 거슬러 줄 수 있다.
📌 답안 예시
n = 1260
count = 0
#큰 단위의 화폐부터 차례대로 확인
coin_types=[500, 100, 50, 10]
for coin in coin_types:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
n %= coin
print(count)
Reference
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저
