[알고리즘 공부] 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm)이란, 최적해를 구하는 데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야할 때마다 그 '순간'에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 최적화 방법이다.

'순간'은 Local하게는 최적이지만, 그 선택을 계속 수집하여 Global하게 해답을 만들었다고 해서 그 결과가 반드시 최적이라는 보장은 없다.

 

 

Greedy 알고리즘이 잘 동작하기 위해서?

 

- Optimal Substructure(최적 부분 구조)

: 부분 문제를 최적화하는 것이 곧 전체를 최적화하는 것이다.

 

- Greedy Chocie Property(탐욕적 선택 속성)

:각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택

 

 

이 두가지 속성을 만족하지 않는다면?

최적해를 보장하지 않지만 근사알고리즘으로 사용이 가능하다. 어느정도의 Loss를 감안하고 사용가능

 

 

DP vs Greedy Algorithm??

- DP는 모든 상황과 교통 정체를 전부 감안하여 최적경로를 찾아내는 것.

//정확하지만 오래걸린다.

- GA는 전체 교통상황은 고려하지 않고 순간순간 교차로가 보일 때마다 차량이 가장 적어보이는 가장 빠른 경로 선택

//빠르지만 때로는 정확하지 않다.

---

예시)

<돈 거슬러 주기>

단, 동전은 500, 100, 50, 10원만 있다고 가정.

 

def greedy(value, coin_list):
    coin_list.sort(reverse=True)

    count = 0
    for coin in coin_list:
        count += value // coin
        value -= (value // coin) * coin

    return count

coin_list=[10, 50, 100, 500]
print(greedy(1260, coin_list))

# 결과값 : 6