그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
단어 그대로 번역하자면 탐욕법이다.
이 부분에서 탐욕적이라 함은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이다.
이 알고리즘은 매 순간 가장 좋아 보이는 것만 선택하고, 그 선택이 나중에 어떤 영향을 미치는지에 대해서는 고려하지 않는다.

거스름돈을 예시로 살펴보자
당신은 음식점의 계산을 도와주는 점원이 되었다고 가정하자.
500원, 100원, 50원, 10원짜리 동전은 무한히 존재한다. 손님에게 거슬러줘야 하는 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구해라
(단, 거슬러줘야 할 돈 N은 항상 10의 배수이다.)

이럴때는 단순하게 가장 가격이 큰 동전 부터 돈을 거슬러 주는 것이다.
이렇게 되면 N원으로 설정된 가격을 금방 차감시켜 0원으로 만들기 적합하다.

coin.py

n = 1260 # 거슬러줘야할 가격
count = 0 # 코인의 개수

# 화폐 단위가 큰 것부터 차례로 거슬러준다.
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 원래 가격을 코인값으로 나눈 몫만큼 동전으로 추가해줌
    n %= coin

print(count)

화폐의 종류가 K개 라고 할때, 위 소스의 시간복잡도는 BigO 표기법으로 O(K)이다. 시간복잡도에서는 총 화폐인 N을 찾을 수 없다.
그래서 이 알고리즘은 동전의 종류에만 영향을 받지 거슬러 줘야하는 금액에는 초점이 맞춰지지 않는다.

알고리즘 문제 유형을 바로 파악하기 어렵다면, 그리디 알고리즘을 의심해 볼 수 있다.

그리디 알고리즘의 예제를 많이 풀어봐야겠다.