[TIL] 내일배움캠프 63일차_[Python] 그리디 알고리즘(Greedy Algorithm)

👀Today I Learn

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 방법으로, 매 순간 가장 좋아 보이는 것을 선택하는 방법
• 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
• 기준에 따라 가장 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 제시함

예제 : 거스름돈

문제

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

문제 해설

• 동전의 최소 개수를 구해야하므로, 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함
• 거스름돈이 N원일 때, 500원으로 최대한 많이 거슬러주고 순서대로 100원, 50원, 10원을 써서 거슬러 주면 됨

문제 풀이(N=1260)

1. 거슬러줘야하는 돈 : 1,260원
   • 점원에게 1,260원이 있고 손님에게 동전으로 거슬러줘야함
   • 500원으로 거슬러 줄 수 있는 돈은 1,000원이므로 거슬러 주면 260원이 남음
2. 남은돈 : 260원
   • 100원으로 거슬러 줄 수 있는 돈은 200원이므로 거슬러주면 60원이 남음
3. 남은돈 : 60원
   • 50원으로 거슬러 줄 수 있는 돈은 50원이므로 거슬러주면 10원이 남음
4. 남은돈 : 10원
   • 10원으로 거슬러 줄 수 있는 돈은 10원이므로 거슬러주면 0원이므로 모두 거슬러줌
5. 결론

   • 총 6개의 동전이 필요

     500원	100원	50원	10원
     2개	2개	1개	1개

코드 구현

def change(n) :
    coins = [500, 100, 50, 10]
    # 동전의 개수
    cnt = 0
		
		# 큰 단위의 화폐부터 차례대로 확인
    for coin in coins :
		    # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
        cnt += n // coin
        # 남은 거스름돈
        n %= coin
    return cnt

result = change(1260)
print(result)

그리디 알고리즘의 정당성

• 모든 알고리즘 문제에 그리디 알고리즘을 적용할 수 있는 것은 아님
• 대부분의 문제는 그리디 알고리즘을 사용하였을 때 ‘최적의 해’를 찾을 수 없을 가능성이 더 많음
• 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토가 필요
  • ex. 800원을 거슬러 줘야 하는데 화폐단위가 500원, 400원, 100원인 경우
    • 그리디 알고리즘으로는 4개의 동전 (500원 + 100원 + 100원 + 100원) 이지만 사실 최적의 해는 2개의 동전 (400원 + 400원)
  • 이런 경우는 정당하지 못하기 때문에 그리디 알고리즘으로 해결 방법을 찾을 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 고민해봐야 함

💡Today I Thought

오늘의 체크리스트

• 알고리즘 코드카타 276-280
• SQL 코드카타 94
• TIL 작성

회고

  명절연휴 시작! 명절연휴는 앞으로 3월말까지 달려야하는 나를 위해 조금 쉬어야지💪라고 하고는 코드카타는 꾸준히 해버리기. 정처기 공부도 해야하는데 요즘 왜이렇게 공부하기 싫은건지(항상 하기 싫어하긴 했음😫) 그래도.. 하는 나.. 제법 멋져..