그리디 알고리즘

그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다.
개인적으로 그리디 알고리즘의 의미(?)를 정말 좋아한다.

해당 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.

대표적인 예시 문제로 '거스름돈 문제' 가 있다.

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야할 동전의 최소 개수를 구하는 문제이다. (단, N은 항상 10의 배수이다.)

이 문제의 해답은 '가장 큰 화폐 단위부터 돈을 거슬러 주는 것' 이다.

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin	# n을 coin으로 나눈 몫 -> 거슬러 줄 동전의 개수
    n %= coin	# 거슬러 주고 남는 값

print(count)
# 결과는 6이다.

화폐의 종류가 K개 일 때, 해당 소스 코드의 시간 복잡도는 O(K)이다.

그리디 알고리즘의 정당성

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다.
하지만 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

예를 들어 n이 800인데 거슬러 줄 수 있는 동전의 단위가 500원, 400원, 100원이라면,
그리디 알고리즘은 500 + 100 + 100 + 100을 거슬러줘야한다고 나올 것이다.
반면 최적의 해는 400 + 400 이다.

따라서 해당 알고리즘을 문제에 적용할 때에는 정당성을 반드시 확인해보아야 한다.

참고

해당 블로그는 나동빈님의 '이것이 취업을 위한 코딩 테스트다. with 파이썬' 교재와 유튜브 강의를 참고하여 작성되었습니다.