[알고리즘] 그리디(Greedy)

그리디 알고리즘
(Greedy Algorithm)

: 각 단계마다 하나의 답을 고르는데, 가장 좋아 보이는 답 선택을 하는 방법.

위의 그림과 같이 단순히 매 상황에서 가장 큰 값을 고르는 알고리즘이다.

대표적인 문제로 거스름돈 문제가 있다.

거스름돈 문제

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

문제 해결 아이디어

• 가장 큰 화폐단위 부터 돈을 거슬러 주기!
• 많은 방법이 있지만, 해당 문제에서는 특히 '최소 개수'를 구하라고 조건을 걸었기 때문에 해당 방법을 선택하였다.
• N원을 거슬러 줘야하는 상황에서, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준 다음,
• 이후에 100원, 50원, 10원 순서대로 거슬러 줄 수 있을 만큼 거슬러주기

정당성 분석

• Q : 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는?
• A : 큰 단위의 동전이 항상 작은 단위의 배수이기에 작은 단위의 동전들을 종합해 다른 해가 나올 수 없도록 하기 위해서

def solution(money):
    answer = 0
    
    # 큰 단위의 화폐부터 차례대로 확인하기
    change = [500, 100, 50, 10]
    remain = money
    for i in change:
        answer += remain // i
        remain = remain % i
    return answer

시간 복잡도 분석

• 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)!
• 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받기 때문
  
  
  
  

관련 문제

📋 백준 1026: 보물
: https://github.com/bmr03016/Coding-Test/blob/main/Baekjoon/%5B1026%5D%20Treasure.ipynb

📋 백준 1448: 삼각형 만들기
: https://github.com/bmr03016/Coding-Test/blob/main/Baekjoon/%5B1448%5D%20%EC%82%BC%EA%B0%81%ED%98%95%20%EB%A7%8C%EB%93%A4%EA%B8%B0.ipynb