[알고리즘][이코테] Greedy Algorithm(그리디 알고리즘)

정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

---

그리디 알고리즘

탐욕법이라고도 불리는 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 것을 말한다.

여러 경우중 하나를 결정해야할 때마다, 매순간 가장 좋아보이는 것을 선택하여 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 이런 방식을 통해 최종적인 해를 구하는 방식이다.

일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

 

그리디 알고리즘의 정당성
그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’를 찾을 수 없을 가능성이 다분하다. 하지만 그리디 알고리즘으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.
따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

 

예시 - 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원으로 무한히 존재한다고 가정한다. 손님에게 거슬러줘야할 돈이 N원일 때, 거슬러줘야할 동전의 최소 개수를 구하라. 단 거슬러 줘야할 돗은 N의 10의 배수이다.

문제 해결 방법

가장 큰 화폐 단위로부터 돈을 거슬러주면 된다. 즉, N원을 거슬러 준다고 할때, 500원→100원→50원→10원 순으로 차례대로 거슬러 줄 수 있는 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수있다.

아래 예시와 같이 거스름돈이 1260이라고 하면 아래와 같이 거스름돈을 줄 수있다.

떠라서 총 6개의 동전으로 거스름돈 1260원을 줄 수 있다. 

 

코드 구현

n=1260 # 거스름돈
count=0
coin_types=[500,100,50,10]
for coin in coin_types:
    count+=n //coin
    n%=coin
print(count)

위의 그림의 설명과 같다. 큰 수의 동전을 먼저 나눠주면 최소개수의 동전으로 나누어줄 수 있게 된다.

 

실전문제

3-2 큰 수의 법칙: https://seung-story.tistory.com/112

3-3 숫자 카드 게임: https://seung-story.tistory.com/113

3-4 1이 될 때 까지: https://seung-story.tistory.com/114