그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm)

개념 및 정의

그리디 알고리즘은 문제 해결의 각 단계에서 지역적으로 최적이라고 생각되는 것을 선택함으로써 전역적인 최적해를 찾으려는 방법입니다. 즉, 각 단계에서 최적의 선택만을 하겠다는 것이 그리디 알고리즘의 기본 아이디어입니다.

장점

1. 간단하고 빠름: 구현이 비교적 간단하고 빠르게 동작합니다.
2. 직관적: 문제를 해결하기 위한 전략이 직관적이므로 이해하기 쉽습니다.
3. 최적해 근사: 모든 경우에 최적의 해를 보장하지는 않지만, 특정 문제에서는 근사치를 빠르게 구할 수 있습니다.

단점

1. 최적해 미보장: 항상 최적의 해를 구할 수 있는 것은 아닙니다.
2. 지역 최적해에 갇힘: 지역적으로 최적인 해를 선택하다보니 전역적으로 최적인 해를 놓칠 가능성이 있습니다.

구현방법

1. 선택 기준 정의: 어떤 기준으로 '최적'이라고 판단할 것인지를 정의합니다.
2. 정렬 or 우선순위 큐 사용: 문제 상황에 따라 정렬이나 우선순위 큐를 사용하여 선택의 기준에 따라 요소를 처리합니다.
3. 반복적 선택: 지역적으로 최적인 요소를 반복적으로 선택하여 해결책을 만듭니다.

예시 코드 (Python)

다음은 그리디 알고리즘을 사용하여 거스름돈 문제를 해결하는 Python 코드 예시입니다.

def greedy_change(money, coins):
    change = []
    for coin in coins:
        while money >= coin:
            change.append(coin)
            money -= coin
    return change

coins = [500, 100, 50, 10]
money = 1260
print(greedy_change(money, coins))

이외에도 다익스트라 알고리즘, 크루스칼 알고리즘, 허프만 코딩 등 여러 알고리즘이 그리디 알고리즘의 원리를 활용합니다.