그리디 알고리즘 (Greedy Algorithm)

#1 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 최적화 문제를 해결하기 위한 알고리즘 디자인 기법 중 하나입니다.

이 기법은 항상 최선의 선택을 하는 것으로 구성되어 있으며, 선택의 결과가 지금 당장은 최적이지만 이후에는 최적이 아닐 수도 있습니다. 이에 따라 그리디 알고리즘은 근사 알고리즘(Approximation Algorithm)으로도 분류됩니다.

 

그리디 알고리즘은 매 순간마다 최선의 선택을 하는 방식으로 동작합니다. 이를 위해서는 대개의 경우 문제에 대한 정렬(Sorting)이 필요합니다. 그리디 알고리즘이 사용될 수 있는

예시로는 다음과 같은 문제들이 있습니다. 

- 거스름돈 문제

- 최소 신장 트리(Minimum Spanning Tree)

- 냅색 문제(Knapsack Problem)

- 탐욕적 스케줄링(Greedy Scheduling)

 

#2 그리디 알고리즘의 특징 

그리디 알고리즘의 장점은 구현이 간단하다는 것입니다.

또한, 문제를 해결하기 위한 모든 가능한 경우의 수를 탐색하지 않아도 되기 때문에 시간 복잡도가 효율적이며, 특히 대규모의 데이터에 대한 문제를 해결하는 데 효과적입니다.

 

하지만 그리디 알고리즘은 최적해를 보장하지 않기 때문에, 최적해가 필요한 문제에 대해서는 사용하기 어렵습니다.

또한, 어떤 선택이 최선인지를 판단하기 위해서는 각 선택지에 대한 정보를 가지고 있어야 하기 때문에 메모리 사용량이 높은 경우에는 사용이 어렵습니다.

 

따라서 그리디 알고리즘은 문제의 특성에 따라서 사용 가능성이 다르며, 효율적인 알고리즘을 설계하기 위해서는 문제를 꼼꼼하게 분석하고 적합한 알고리즘 디자인 기법을 선택하는 것이 중요합니다.

 

#3 대표적인 예시(거스름돈 문제)

동전의 최소 개수 구하는 문제를 그리디 알고리즘으로 푸는 의사코드는 다음과 같습니다.

1. 지불해야 할 금액을 입력받는다.
2. 지불 가능한 동전의 종류를 입력받는다.
3. 동전 종류를 내림차순으로 정렬한다.
4. 현재 가지고 있는 동전 중 가장 큰 동전을 선택한다.
5. 선택한 동전으로 가능한 최대한의 금액을 지불한다.
6. 지불한 금액을 입력받은 금액에서 빼고, 지불한 동전의 개수를 1 증가시킨다.
7. 4번부터 6번까지 반복하면서 지불할 금액이 0이 될 때까지 지불을 계속한다.
8. 지불한 동전의 개수를 출력한다.

아래는 파이썬으로 구현한 코드입니다. 

def min_coin_count(value, coin_list):
    coin_list.sort(reverse=True) # 동전 종류 내림차순으로 정렬
    count = 0
    for coin in coin_list:
        coin_num = value // coin # 해당 동전으로 지불할 수 있는 개수 계산
        count += coin_num # 동전의 개수 더하기
        value -= coin * coin_num # 지불한 금액 빼기
        if value == 0: # 지불할 금액이 0원이면 종료
            break
    return count

 

이 함수는 value에 지불해야 할 금액을 입력하고, coin_list에 지불 가능한 동전의 종류를 리스트로 입력하면, 동전의 최소 개수를 반환합니다. 예를 들어, min_coin_count(830, [500, 100, 50, 10])을 호출하면 7을 반환합니다.