[이코테] Chapter3-1 / 당장 좋은 것만 선택하는 그리디

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 "탐욕법"으로 소개된다.
이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
여기에서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.
그리디 알고리즘은 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교 했을 때, '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다.
반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 

예를 들어 여러 개의 데이터를 빠르게 정렬해야 하는 문제는 정렬 라이브러리의 사용 방법을 알고 있어야 한다.
또 다른 예시로 최단경로를 빠르게 찾아야 하는 문제는 플로이드 워셜 혹은 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있거나 팀 노트를 통해 준비해야 풀 수 있다. 
참고로 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘으로 분류되므로, 그리디 알고리즘이면서도 '암기'가 필요한 알고리즘이기도 하다.
다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다는 점을 이해하자.

이외에도 그리디 알고리즘 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 사전 지식 없이도 풀 수 있는 문제도 있겠지만, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다.
향후 등장할 문제를 풀어보면 이해할 수 있을 것이다.

보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 떄 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘 이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

이제 '거스름돈' 문제를 예로 그리디 알고리즘을 설명하겠다.
"거스름돈' 문제는 그리디 알고리즘을 대표하는 문제이다.

거스름돈(예제 3-1)

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 1chrl00원 50원, 10원 짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라, 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제 해설

이 문제는 그리디 알고리즘을 이요해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.
그것은 바로 '가장 큰 화폐 단위부터 돈을 거슬러 주는 것' 이다. 
N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.
그 다음 100원, 50원, 10원 짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

예를 들어 입력으로 주어진 N이 1,260이라면 다음과 같이 가장 큰 화폐 단위부터 거슬러 주는 과정을 통해 1,260원을 모두 거슬러 줄 수 있다.

Step 0 - 초기 단계 - 남은 돈: 1260원 
Step 1 - 남은 돈: 260원 (1,260원에서 500원 짜리로 거슬러 줄 수 있는 돈은 1,000원, 즉 500원 2개로 1000원을 거슬러 줌)
Step 2 - 남은 돈 : 60원 (앞 단계에서 남은 돈은 260원, 그중 100원 단위로 거슬러 줄 수 있는 돈은 200원, 즉 100원 2개이고 남은 돈은 60원)
Step 3 - 남은 돈 : 10원앞 단계에서 남은 돈 60원에서 50원 단위로 거슬러줄 수 있는 돈은 50원 1개이고, 남은 돈은 10원)
Step 4 - 남은 돈:  0원 (이제 남은 돈은 10원이고, 10원 1개를 거슬러 주며 거스름돈 계산 끝)

즉, N이 1,260일 때, 손님이 받은 동전의 최소 개수는 6개 이다. 
이 내용을 파이썬으로 작성하면 아래와 같다.

n = 1260
count = 0

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

for coin in coin_types:
    count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n = n % coin
print(count)

코드를 보면 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 K개 라고 할 때 위소스 코드의 시간 복잡도는 O(K)이다. 참고로 시간 복잡도에서 거슬러 주어야 할 돈 N은 찾아볼 수 없는 것을 알 수 있다.
즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.

물론 실제 코딩 테스트에 출제되는 그리디 유형의 문제는 위와 같은 거스름돈 문제보다는 일반적으로 난이도가 높은 편이다. 하지만 문제에 접근하는 방법은 유사하므로 거스름돈 문제는 그리디 알고리즘을 설명할 때 자주 소개되는 문제이다.

그리디 알고리즘

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다.
대부분의 문제는 그리디 알고리즘을 이용했을 때, '최적의 해'를 찾을 수 없을 가능성이 다분하다.
하지만 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는, 그 해법이 정당한지 검토해야 한다.
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를 들어 800원을 거슬러 줘야 하는데, 화폐 단위가 500원, 400원, 100원인 경우를 생각해보자.
이 경우에 그리디 알고리즘으로는 4개의 동전(500원 + 100원 + 100원)을 거슬러 줘야 한다고 나오는데, 최적의 해는 2개의 동전(400원 + 400원)을 거슬러 주는 것이다.

다시 말해  (예제3-1)문제에서는 큰 단위가 작은 단위의 배수 형태이므로, '가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다'는 아이디어는 정당하다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면, 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그떄는 이후의 장에서 다루게 될 다이나믹 프로그래밍이나 그래플 알고리즘 등으로 문제를 해결할 수 있는 지를 재차 고민해보는 것도 한 방법이다.

처음에 문제를 만났을 때는 이것저것 다양한 아이디어를 고려해야 한다.
가장 먼저 '10원짜리로만 모두 거슬러 주도록 코드를 작성하면 어떻게 되지? 라고 생각할 수 있다. 그 이후에는 '10원짜리로만 모두 거슬러 주면 최적의 해를 구할 수 없겠구나!'라고 문제점을 인식하고, 가능한 또 다른 문제 풀이 방법을 하나씩 곰곰이 생각해보는 것이다. 그러다가 결국엔 '가장 큰 500원짜리부터 거슬러서 가장 작은 10원짜리까지 차례대로 거슬러 준다면, 어떻게 될까? 라고 생각을 하고, '거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로, 이렇게 하면 항상 최적의 해를 보장할 수 있겠구나!'까지 떠올릴 수 있어야 문제의 정답 판정을 받을 수 있을 것이다.

실제로 거스름돈 문제에서 동전(화폐)의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로는 해결할수 없다. 화폥의 단위가 무작위로 주어진 문제는 2부에서 배울 다이나믹 프로그래밍으로 해결할 수 있으며 해당 문제 또한 책에서 다루고 있다(8장 '효율적인 화폐구성').

지금까지 그리디 알고리즘의 기본 원리에 대해서 알아보았으므로 이제부터 그리디 알고리즘의 실전 예제를 더 풀어보자. 지금부터 설명할 문제는 알고리즘 대회 및 코딩 테스트에 출제되었던 문제를 다듬은 것이다. 기업의 코딩테스트를 안정적으로 통과하려면 다음에 소개되는 문제 각각에 대해 문제별 아이디어를 떠올리고 코드로 작성하기까지 시간이 30분 이내로 소요되어야 한다. 난이도는 모두 '하'에 해당하며 총 3문제를 준비하였다.

다음글 참고 바람.