[알고리즘] 그리디 알고리즘(탐욕법)

그리디 알고리즘이란 ?

주어진 상황에서 가장 좋은것(큰 값)을 구하는 알고리즘이다.

단순히 가장 좋은것을 선택하는 행위를 반복하여도 최적의 값이 추출되는지 검증이 필요하다.

 

 

<나동빈 유튜브 - 그리디알고리즘 https://www.youtube.com/watch?v=2zjoKjt97vQ>

1. 해결 아이디어 제시

거스름돈으로 사용할 화폐단위를 정의한다.

가장 적은 개수를 구하는 문제이기에 화폐단위중 가장 큰 값으로 거슬러 줄수 있는 개수를 구한다.

그다음으로 적은 금액으로 거슬러 줄 수 있는 개수를 구한다.

해당 작업을 반복한다.

---

2. 정당성 분석

해당 문제는 거슬러 주어야할 최소 동전 개수를 구하는 문제 이기에, 화폐의 가장큰 단위로 거슬러 준다면 , 거스름돈의 개수를 최소화할 수 있다.

예 : 거스름돈 1,000 일 경우

500 * 2 

100 * 10

50 * 20

10 * 100

이기에 가장큰 화폐단위인 500원으로 거슬러 주었을 때가 가장 최적의 방법이다.

---

3. 코딩

d = 1270

array = [500,100,50,10]

count = 0

for coin in array:

count += d // coin

d%=coin

print(count)

---

화폐의 종류가 K 라고한다면

시간 복잡도는 O(K)이다.