[이것이 코딩 테스트다] 그리디 <1. 당장 좋은 것만 선택하는 그리디>

📚그리디Greedy

그리디 알고리즘은 영어 그대로 번역하여 '탐욕법' 으로 소개된다.
여기서 '탐욕법' 은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로' 혹은, '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이루어 출제된다.

---

[예제 1] 거스름돈

<문제> : 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

n = int(input("거스름돈: "))
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for i in coin_types:
    count += n // i # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= i

print("동전의 최소 개수: ", count, "개")

<해설> : 코드를 보면 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 K개라고 할 때 위 소스 코드의 시간 복잡도는 O(K)이다.

즉, 이 알고리즘의 시간 복잡도는 거슬러 줘야 할 금액의 크기와는 무관하고 동전의 총 종류에만 영향을 받는 것을 알 수 있다.

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.