그리디 알고리즘이란?

어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

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

대표 예제

거스름돈

문제

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

해설

가장 큰 화폐 단위부터 돈을 거슬러 주면 답을 구할 수 있다. 가장 큰 500원, 100원, 50원, 10원을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

n = 1260
count = 0

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

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

print(count)

화폐의 종류만큼 반복을 수행해야 하므로 시간 복잡도는 O(K)이다.

그리디 알고리즘의 정당성

대부분의 문제는 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 있다. 따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 위의 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 예를 들어 800원을 거슬러 줘야 하는데, 화폐 단위가 500원, 400원, 100원일 경우에는 그리디 알고리즘으로는 4개(500+100+100+100)이 나오지만 최적의 해는 2개(400+400)이다.

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하자. 오랜 시간을 고민해도 해결 방법을 찾을 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘 등을 고민하자.

참고문헌

이것이 코딩 테스트다 with 파이썬 - 나동빈