그리디

그리디 알고리즘이란?

- 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘
- 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려 x

 

1. 단순히 현재 상황에서 가장 좋아 보이는 것만  반복적으로 선택해도 최적의 해를 구할 수 있는가

2. 정당한가(정당성 분석)

 

tip. 기준에 따라 좋은 것을 선택함으로 문제에서 "가장" 에 대한 기준을 알게 모르게 제시해 줌.

---

ex) 거스름 돈

닫기

닫기

#거스름 돈 문제(3_1)

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n//coin
    n %= coin
    
print(count)

1. 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨.

2. 코인 타입의 큰 단위가 작은 단위의 배수 형태이기 때문에 정당함.

시간 복잡도 : O(k), k = 화폐 종류의 개수

 

---

이것이 코딩 테스트다 - 나동빈
정리하긔
https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2