[Algorithm] 12 강 : 그리디 알고리즘 개요(탐욕법)

그리디 알고리즘이란?

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것 만 고르는 방법

그리디 해법은 그 정당성 분석이 중요

- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요

 

 

 

여기서 최적의 해는 가장 큰값인 21 이다. 

 

 

하지만 그리디 해는 현재노드(현재 상황) 에서 가장 큰 값을 거치는 것을 의미한다.

 

그래서 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

 

---

 

예시) 거스름돈 문제

이 상황에서 예를들어 거스름돈이 1260이라고 가정한다. 여기서 카운터에서 손님에게 거스러줄 동전의 최소의 개수는

 

동전이 가장 큰 값부터 주면된다. 

 

500 원  * 2  / 100원*2 / 50원 * 1 / 10원 * 1

이렇게가 된다. 현재 상황에서 큰 금액에서부터 줄수 있는 최대한을 주면 된다. 이렇게 그리디 알고리즘을 통해 문제를 풀수 있다. 

 

이때 정당성 분석이 필요하다. 이 그리디 알고리즘이 최적의 해를 보장하는 이유를 찾아야한다. 

- 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수 이므로 작은 단위의 동전을 종합해 다른 해가 나올수 없기 때문에 최적의 해를 보장한다. 

 

 

이렇게 그리디 알고리즘 문제에서는 아이디어를 떠올리고 이것이 정당한지 검토해야 된다.

 

n = 1260
count = 0

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

for coin in array:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)
=> 6

 

---

 

시간 복잡도 분석

화폐의 종류가 K 라고 할 때 , 소스코드이 시간 복잡도는 O(K)이다.

이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

 

 

---

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.

참고 : www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC