그리디 알고리즘

<이것이 취업을 위한 코딩 테스트다>를 보고 공부중인 내용입니다..

특징

• 단순하지만 강력한 문제 해결 방법
• greedy 하다… ⇒ 탐욕적이다 ⇒ ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’ ⇒ 나중에 미칠 영향은 알 필요 없다.
• 정렬 알고리즘과의 합작 필요

거스름돈 예제

문제

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

해설

🍀 ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주기 ⇒ 500원을 최대로 활용하자! 그 다음은 100→50→10원 순,,

예시: N=1,260 이라면?

코드

N=int(input()) #금액 입력 받기

coin=[500,100,50,10] #동전 단위 저장
cnt=0 #누적 동전 개수

for i in coin:
    cnt+=N//i #개수 저장
    N%=i #남은 금액 갱신

print(cnt)

• 위 코드는 화폐 단위 종류만큼 반복되기 때문에 시간복잡도는 화폐의 종류가 K라고 할 때, O(K)가 된다.
• 시간 복잡도에 영향을 주는 요소: 금액이 아닌 화폐의 종류 개수!

생각해 봐야할 점

• 만약, 화폐 단위가 500원, 400원, 100원이고 거스름돈이 800원이면, 그리디 알고리즘으로 풀면 500x1+100x3으로 총 4개가 필요하다. 그러나, 실제 최적의 해는 400x2로 2개만 있으면 된다.
• 거스름돈 문제에서 화폐의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로 해결 ❌ ⇒ 다이나믹 프로그래밍