그리디 알고리즘 ( Greedy Algorithm )

• 그리디 알고리즘( Greedy Algorithm )
  
  그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
  
  단어 그대로 번역 하면 탐욕법 이고 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 이다.
  
  여기서 탐욕적 이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
  
  매 순간 가장 좋아 보이는 것을 선택하며 , 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
  
  
  
  
  
• 코딩 테스트 유형
  
  그리디의 문제 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높다.
  
  최단 경로를 구하는 다익스트라 알고리즘은 그리디 알고리즘으로 분류 되므로 암기가 필요한 알고리즘 이다.
  
  그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에 다익스트라 알고리즘과 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다.
  
  보통 창의력, 즉 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
  
  문제에 따라 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해 준다.
  
  그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
  
  
  
  
  
• 대표적인 그리디 알고리즘 예제 : 거스름돈 문제
  
  거스름돈이 500원, 100원, 50원, 10원 짜리 동전이 무한이 존재한다 가정 할때
  
  손님에게 거슬러 줘야 할 돈이 N원일때 거슬러 줘야 할 동전의 최소 개수를 구하자.
  (단 N은 항상 10의 배수)
  
  
  예를 들어 N 을 1260원을 거슬러 줘야 된다고 생각해보자.
  
  그러면 500원 2개, 100원 2개,  50원 1개, 10원 1개로 총 6개의 동전을 거슬러 줘야한다.
  
  즉 가장 큰 화폐 단위부터 돈을 거슬러 주는 것 이다.
  
  

  # python code
  
  N = int(input())
  coin = [500, 100, 50, 10]
  cnt = 0 # 거스름돈의 갯수
  
  for i in coin:      # 500원 짜리 동전부터 계산
      cnt += (N // i) # 사용한 동전 갯수 만큼 더해준다.
      N %= i          # 연산후 남은 금액
          
  print(cnt)

  
  
  이 문제는 큰 단위의 화폐가 작은 단위의 배수 형태이므로, 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 되므로 이 아이디어는 정당하다.
  
  
  
• 그리디 알고리즘의 정당성
  
  모든 알고리즘 문제에 그리디 알고리즘을 적용할 수 있는 것은 아니다.
  
  대부분의 문제는 그리디 알고리즘을 이용했을때 '최적의 해'를 찾을 수 없을 가능 성이 더 많다.
  
  그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

ex )  800원을 거슬러 줘야 하는데 화폐단위가 500원, 400원, 100원인 경우

그리디 알고리즘으로는 4개의 동전 (500원 + 100원 + 100원 + 100원) 이지만

사실 최적의 해는 2개의 동전 (400원 + 400원) 이다.

이런 경우는 정당하지 못하기 때문에 그리디 알고리즘으로 해결 방법을 찾을 수 없다면
다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 고민해 봐야 한다.

출처 : 이것이 코딩테스트다 with 파이썬

 

그리디 알고리즘의 또 대표 문제로는 아래와 같은 문제가 있다.

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달