그리디 알고리즘(Greedy Algorithm)

그리디(Greedy) 알고리즘

---

🎈개념

- 탐욕 알고리즘이라고 불리며, 여러 경우 중 하나를 결정해야 할 때 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법

- 그리디 알고리즘은 최적 해를 구하는데 사용되는 근시안적인 방법

- 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 통해 최종적인 해답을 만들었다고 해서 그것이 최적이라는 보장이 없는 계획법

 

---

🎈그리디 알고리즘의 조건

1. 탐욕스러운 선택 조건
   - 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 함. "안전하다"라는 의미는 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것.
2. 그리디 알고리즘을 사용해 결과 도출 시 최적해가 무조건 나오나?
   - 그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아님!
   but, 그리디 알고리즘을 사용해 푸는 문제가 나왔을 때
   이 조건이 만족되는가? 를 생각해 충족되면 그리디 알고리즘을 사용.
   즉, 그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제함.
3. 최적 부분 구조 조건
   - 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다라는 조건
   이 말은 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다는 것

그리디 알고리즘에서 고려해야 하는 상황은 값들이 서로 영향을 주면 안된다는 것을 염두에 두어야 함!

 

---

🎈대표적인 그리디 알고리즘 예제 - 동전 교환 문제

# greedy 동전교환 문제
coin=[500,100,50,10]
change=int(input())
answer=0   # 동전 몇개 사용했는지 최소값
index=0
while(1):
    cnt=change//coin[index] # index가 0일때.. cnt 500 동전 사용 개수
    change-=(cnt*coin[index]) # 거슬러 줄 돈에서 동전갯수*500 빼주기
    answer+=cnt
    index+=1   # 인덱스 1 증가 시켜서 100짜리 동전 사용할 준비
    if index==4:
        break
print(answer)

 

Reference

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98