[알고리즘] 그리디 알고리즘의 개념과 거스름돈 문제풀이의 한계점

그리디 알고리즘 (Greedy) : 탐욕법. 매순간 가장 좋아보이는 것 선택, 이 선택이 나중에 미칠 영향에 대해서는 고려X

예시 1 : 거스름돈 문제 - 거슬러줘야할 동전의 최소 개수 구하기

- 가장 큰 화폐부터 거슬러주기

#python
n= int(input()) #가격은 10의 배수
count=0

for coin in [500,100,50,10]: #배수임
  count+=n//coin
  n=n%coin

print(count)

※ 가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수이므로 그리디로 풀 수 있다.

 

그리디 알고리즘이 먹히지 않는 거스름돈 문제

예시 2 : 800원을 거슬러줘야하는데 화폐단위 500원, 400원, 100원 (배수가 아님)

- 그리디로 문제풀이 : 500원 + 100원 + 100원 + 100원
- 사실상 최적의 해 : 400원 + 400원

  → 정렬 알고리즘을 사용했을때 만족 시킬수 있음

 

코딩테스트 접근법

바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 먼저 의심!
문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.
그래도 해결이 안된다면 다이나믹 프로그래밍이나 그래프 알고리즘으로 접근.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬