Greedy Algorithm(그리디 알고리즘)

Greedy Algorithm?

- 단순하면서 강력한 문제 해결법

- 탐욕적으로 문제 푸는 알고리즘

- 매 순간 가장 좋아보이는 것을 선택, 현재의 선택이 나중에 미칠 영향은 고려X

=> 그리디 알고리즘 문제는 "가장 큰 순서대로", "가장 작은 순서대로"라는 기준을 제시.

=> 정렬 알고리즘과 짝을 이뤄서 출제.

 

탐욕적 

=> 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

 

ex) 거스름돈 문제 => 대표적인 그리디 알고리즘 문제

- 500, 100, 50, 10원 짜리 동전이 무한히 존재.

- 손님에게 거슬러 줘야 할 동전의 최소 개수?

"가장 큰 단위부터 거슬러주는 것"이 문제 해결 방법

n = int(input())
cnt=0
arr=[500,100,50,10] # 그리디 알고리즘은 큰 단위 -> 작은 단위로

for i in arr:
    cnt += n//i
    n%=i
print(cnt)

 

그리디 알고리즘은 모든 알고리즘 문제에 적용X

 

=> 대부분의 그리디 문제에서는 풀이를 위한 최소한의 아이디어를 떠올리고, 정당한지 검토!!!

 

1. 문제 유형 파악하기 어려우면 그리디 의심.

2. 그리디로 해결 할 수 없다면 다이나믹 or 그래프 등으로 풀 수 있는건지 고민.