알고리즘 - 그리디 알고리즘

이번 포스트에서는 그리디 알고리즘에 대해 알아보겠습니다.

해당 내용은 나동빈 님이 집필하신 이것이 취업을 위한 코딩테스트다 with 파이썬 을 보며 공부한 내용을 토대로 작성하였습니다.

---

그리디 알고리즘

그리디 알고리즘이란 국내에서 흔히 탐욕법으로도 소개되곤 합니다. 이 알고리즘은 말 그대로 단순하게 탐욕적으로 문제를 해결하는 하나의 방식을 말합니다.

매 순간 가장 최선의 선택을 하여 문제를 푸는 알고리즘이기 때문에 정렬 알고리즘과 짝을 이뤄서 출제가 되는 경향이 있습니다.

그리디 알고리즘 문제는 다른 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 문제를 해결할 수 있는 가능성 이 높습니다.

하지만 그리디 알고리즘 문제의 유형의 폭이 굉장히 넓기 때문에 모든 문제를 숙련도 없이 접근해서 해결하기는 어렵습니다.

---

그렇다면 그리디 알고리즘을 통해 문제를 해결하는 방법에 대해 알아보도록 하겠습니다.

그리디 알고리즘의 핵심은 문제를 해결하기 위한 최소한의 아이디어를 떠올리고 그것에 맞는지 검토할 수 있어야한다는 것 입니다.

그리디 알고리즘의 가장 유명한 예제인 거스름돈 문제를 살펴보겠습니다.

거스름돈

카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한히 있다고 가정한다. 손님에게 거슬러줘야할 돈이 N원일때

거슬러줘야할 동전의 최소 개수를 구하라. 단, 거슬러줘야할 돈 N은 항상 10의 배수이다.

---

이 문제는 거슬러줘야하는 동전의 최소 갯수를 구하는 문제입니다. 그리디 알고리즘을 설명하는데 빠지지 않고나오는 문제입니다.

이 문제의 핵심은 거슬러 줘야하는 동전의 최소 갯수 입니다. 최소 갯수를 구하기 위해서는 가지고 있는 거스름돈의 목록을 정렬해야합니다.

가장 큰 돈부터 거슬러줘야 최소한의 갯수가 나오기 때문입니다. 

예를들어 1000원의 거스름돈을 거슬러줄 때 

• 500원 부터 거슬러주면 거스름돈의 갯수 : 2개
• 100원부터 거슬러주면 거스름돈의 갯수: 10개

이렇게 차이가 나기 때문입니다. 그리디 알고리즘의 핵심은 매 순간 최선의 선택을 하는 것 입니다.

이 문제를 코드로 옮겨보면

n = int(input()) # 거슬러줘야할 돈 입력
count = 0

coinList = [500, 100, 50, 10] # 현재 가지고 있는 거스름돈 목록 - 정렬된 상태라고 가정

for coin in coinList:
	count += n // coin
    n %= coin
    
print(count)

이런 코드가 됩니다.

---

그리디 알고리즘은 매 순간마다 최선을 택하는 알고리즘입니다. 때문에 항상 선택한 값이 문제의 정답일수는 없습니다.

그리디 알고리즘이 사용가능한 경우가 있고, 아닌 경우도 있기 때문에 잘 판단해서 사용하시길 바랍니다.

문제 지문을 읽으시다 최소한의 경우, 최소 값 등등의 지문이 나오면 그리디 알고리즘 사용을 고려해보시는 것도 좋은 방법일 것 같습니다!