그리디 알고리즘은 가장 단순하면서도 강력한 문제 해결 방법이다. 그리디라는 단어의 뜻처럼, 문제를 단순 무식하게, 탐욕적으로 해결하는 알고리즘이다. 즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 그리디 알고리즘은 현재 상황에 대해서만 고려할 뿐, 현재의 선택이 나중에 미칠 영향은 전혀 고려하지 않는다. 그리디 알고리즘은 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형이다. 우리가 그리디 알고리즘이라는 의미를 모르더라도, 쉽게 생각해내고 접근할 수 있는 알고리즘이라는 의미이다. 하지만 그리디 알고리즘을 적용할 수 있는 문제 유형은 무수히 많기때문에, 많은 유형의 문제를 접해보고 풀어보면서 연습해야한다.
그리디 알고리즘을 가장 쉽게 이해할 수 있는 대표적인 예제는 '거스름돈' 문제이다.
카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 갯수를 구하여라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
이 문제는 그리디 알고리즘을 몰라도 쉽게 해결할 수 있는 문제이다. 핵심은 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다. 만약 입력으로 주어진 N이 1260원이라면 다음과 같은 과정으로 해결할 수 있다.
- 먼저 가장 큰 화폐 단위인 500원을 거슬러 줄 수 있는 만큼 거슬러 준다.
(500원 동전 2개) - 다음으로 큰 화폐 단위인 100원을 거슬러 줄 수 있는 만큼 거슬러 준다.
(100원 동전 2개) - 다음으로 큰 화폐 단위인 50원을 거슬러 줄 수 있는 만큼 거슬러 준다.
(50원 동전 1개) - 마지막 화폐 단위인 10원을 거슬러 줄 수 있는 만큼 거슬러 준다.
(10원 동전 1개) - 결국 손님이 받은 동전의 최소 갯수는 6개이다. 이 내용을 코드로 작성하면 다음과 같다.
결국 손님이 받은 동전의 최소 갯수는 6개이다. 이 내용을 코드로 작성하면 다음과 같다.
n = 1260
count = 0
coint_types = [500, 100, 50, 10]
for coin in coin_types :
count += n // coin
n %= coin
print(count)그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제에 그리디 알고리즘을 적용하였을 때 최적의 해를 찾을 수 없는 가능성이 크다. 따라서 그리디 알고리즘을 이용하여 해법을 찾았을 때, 우리는 그 해법이 정당한지 확인해야할 필요가 있다. 위에서 설명한 거스름돈 문제의 경우, 큰 화폐 단위가 작은 화폐 단위의 배수이기때문에 그리디 알고리즘을 적용하여 문제를 해결할 수 있었다. 만약 800원을 거슬러 줘야 하는데, 화폐 단위가 500원, 400원, 100원이라면 어떻게 될까? 이 경우 그리디 알고리즘을 적용한다면, 총 4개의 동전(500원 + 100원 + 100원 + 100원)을 거슬러 줘야 하는데, 최적의 해는 2개의 동전(400원 + 400원)을 거슬러 주는 것이다. 즉, 그리디 알고리즘은 항상 최적의 해를 찾아주는 것이 아니기때문에 해법의 정당성에 대한 검증이 필요하다.
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 지음
