TIL_25 : Greedy Algorithm

🙄 Greedy Algorithm

---

➡ Greedy Algorithm?

• 미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식

• 장점 : 간단하고 빠르다

• 단점 : 최적의 답이 보장되지 않는다

🙄 언제 Greedy Algorithm 사용할까

---

• 다른 알고리즘들이 너무 느려서 사용할 수 없는 수준일 때

• 처음부터 최적의 답이 필요 없고 적당한 답을 원할 때

제일 좋은 상황은 Greedy Algorithm으로 최적을 답을 구하는 것!!

➡ Greedy Algorithm이 최적의 답을 보장하는 문제의 조건

1. 최적 부분 구조 (Optimal Substructure)
   : 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것

2. 탐욕적 선택 속성 (Greedy Choice Property)
   : 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택

위 두 가지 조건을 갖춘 문제라면 Greedy Algorithm이 최적의 솔루션 보장

🙄 최소 동전으로 거슬러 주기

---

def min_coin_count(value, coin_list):
    default_coin_list.sort(reverse=True)
    coin = 0
    for i in range(4):
        coin += value // default_coin_list[i]
        rest = value % default_coin_list[i]
        value = rest
    return coin
 
 
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))

# 10
# 5
# 49