[그리디] 그리디 알고리즘 (1) 개념

그리디 알고리즘

• '탐욕법'
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법 
• 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려 X
• 사전 지식이 없어도 풀 수 있음
• 그리디 알고리즘 유형의 문제는 매우 다양 ➡️ 많은 유형 접해보기
• 기준에 따라 좋은 것을 선택하는 알고리즘
  • 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줌
  • 자주 정렬 알고리즘과 짝을 이뤄 출제

그리디 알고리즘 예제 - 거스름돈

이코테 p.87 예제 3-1

 

정답 소스코드:

import sys

N = int(sys.stdin.readline().rstrip())
cnt = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
  cnt += N // coin # 현재 화폐로 거슬러 줄 수 있는 동전의 개수
  N %= coin # 현재 화폐로 거슬러 준 후 남은 돈

print(cnt)

최소 개수의 동전을 거슬러 주려면 가장 화폐 단위가 큰 순서 대로 거슬러 주어야 함. 따라서 500원부터 차례대로 거슬러 줄 수 있는 동전의 개수를 카운트하고, 거슬러줘야 할 남은 돈을 계산하면 됨.

이때, 화폐의 종류를 K개라고 하면 시간복잡도는 O(K)임. 시간복잡도는 화폐의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기 N과는 무관

그리디 알고리즘의 정당성

• 문제에 따라 그리디 알고리즘 적용 시 최적의 해를 찾을 수 없을 가능성 존재
• 그리디 알고리즘으로 문제의 해법을 찾았을 경우, 그 해법이 정당한지 검토 필요
• 거스름돈 예제를 그리디 알고리즘으로 해결할 수 있는 이유: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
  • 만약 화폐 단위가 [500, 400, 100]일 때 800원을 거슬러 주는 경우: 400원 2개가 최적의 해임
• 거스름돈 문제에서 화폐 단위가 서로 배수 형태가 아니라, 무작위라면 그리디 알고리즘으로 해결 불가
  • 다이나믹 프로그래밍으로 해결