개요
코딩 테스트 준비를 위해 스터디에 들어가게 되었습니다. 이번 주차의 내용은 그리디에 관한 내용이었고, 이에 대한 이론적인 내용을 글로 정리해보는 시간을 가져보겠습니다.
그리디 알고리즘
-
단순하지만 강력한 문제 해결 방법
-
어떠한 문제가 있을 때, 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 이다.
-
여기서 탐욕적이란 말의 의미는 "현재의 선택이 나중에 미칠 영향은 고려하지 않고, 지금 당장 좋은 것만 고르는 방법"을 의미한다.
-
그리디 알고리즘은 정당성 분석이 중요하다!
단순히 가장 좋은 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다.
-
기준에 따라 좋은 것을 선택하는 알고리즘 -> 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
(대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로, 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제 된다.)
예제 문제
- 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다고 가정하자. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구해라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
이 문제는 그리디 알고리즘으로 풀 수 있는 대표적인 문제
간단한 아이디어만 떠올리면 문제를 해결할 수 있다.
"가장 큰 화폐 단위부터 돈을 거슬러 주는 것"
아이디어 설명
만약, 1260원을 거슬러줘야 한다고 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 이 후, 그 다음 화폐 단위인 100원, 50원, 10원 짜리 동전을 차례대로 거슬러 주면 최소의 동전 개수로 거슬러줄 수 있다.
그림 설명
거스름돈 : 1260
거스름돈 : 260 (500원 2개로 거슬러줌)
거스름돈 : 60 (100원 2개로 거슬러줌)
거스름돈 : 10 (50원 1개로 거슬러줌)
거스름돈 : 0 (10원 1개로 거슬러줌)
코드
n = 1260
count = 0
coins = [500,100,50,10]
for coin in coins:
count+= n//coin
n%=coin
print(count)- 동전의 종류만큼 반복 수행
- 따라서 동전의 종류가 K개라고 할 때 위 코드의 시간 복잡도는 O(K)이다.
- 시간 복잡도는 동전의 총 종류 에만 영향을 받지, 거슬러줘야 하는 금액과는 무관하다.
그리디 알고리즘의 정당성
- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.
- 거스름돈 문제에서 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 "큰 단위"가 항상 "작은 단위의 배수"이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
위 아이디어의 반례
만약 800원을 거슬러 줘야 하는데, 화폐 단위가 500원,400원,100원인 경우를 생각해보자.
-
이 경우에는 그리디 알고리즘으로는 4개의 동전(500원 1개, 100원 3개)를 거슬러 줘야 한다고 나온다.
-
하지만 최적의 해는 2개의 동전(400원 2개)을 거슬러주는 것이다.
- (400이 500의 배수가 아니기 때문에 발생한 문제)
-
우리가 해결한 거스름돈 문제에서는 가장 큰 단위의 화폐가 항상 가장 작은 단위의 배수 이다.
-
따라서, 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다라는 아이디어는 정당하다.
대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
나가면서
오늘은 그리디 알고리즘에 대해 공부하는 시간을 가졌습니다. 그리디 알고리즘은 문제를 풀며 정당성을 보장할 수 있도록 많은 문제를 풀어나가며 감을 더 익혀야 될 것 같습니다.
