그리디 알고리즘? (Greedy, 탐욕 알고리즘)

📌그리디 알고리즘이란?

 

그리디 알고리즘(탐욕 알고리즘, Greedy Algorithm)은 문제를 해결할 때 현재 시점에서 가장 최선의 선택(탐욕적인 선택)을 반복적으로 수행하여 최종 해답에 도달하는 알고리즘 기법입니다. 이 알고리즘은 각 단계에서 가능한 최적의 선택을 하지만, 그 선택이 전체 문제에 대해서도 최적해를 보장하는지에 대해서는 문제마다 다릅니다.

 

---

🙄 그리디 알고리즘의 기본 원리

1. 선택의 기준: 매 단계에서 가장 좋은 선택(탐욕적 선택)을 합니다.
2. 최적 부분 구조: 전체 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법들로 구성될 수 있어야 합니다.
3. 일관된 선택: 그리디 알고리즘이 적용 가능한 문제는 이렇게 매 순간의 선택이 최종 결과에도 영향을 미치지 않고, 항상 최적해를 보장하는 경우여야 합니다.

 

😀 적용 예시

• 거스름돈 문제: 500원, 100원, 50원, 10원의 동전이 있을 때, 최소 동전의 개수로 거스름돈을 주는 문제는 그리디 알고리즘으로 풀 수 있습니다. 큰 단위의 동전부터 가능한 한 많이 주면 최적의 해를 구할 수 있습니다.
• 활동 선택 문제: 여러 개의 활동 중에서 시간이 겹치지 않게 가장 많은 활동을 선택하는 문제에서는 가장 빨리 끝나는 활동부터 선택하면 최적의 해를 얻을 수 있습니다.

---

장단점

• 장점: 구현이 간단하며, 계산 속도가 빠릅니다.
• 단점: 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니며, 어떤 문제에서는 오히려 잘못된 해를 구할 수 있습니다.

따라서 그리디 알고리즘을 사용할 때는 그 선택이 최종적으로 최적해를 보장하는 문제인지를 판단하는 것이 중요합니다.

 

 

 

구현 예시 (최소 동전 개수 구하기)

def get_min_coins(change):
    # 동전 단위 (내림차순으로 정렬)
    coins = [500, 100, 50, 10]
    
    # 동전의 개수를 저장
    count = 0
    
    # 각 동전 단위별로 최대 개수 사용
    for coin in coins:
        count += change // coin  # 해당 동전으로 줄 수 있는 개수
        change %= coin  # 나머지 금액을 갱신
        
    return count