Python 코딩테스트 02: 그리디 알고리즘

그리디 알고리즘: 최적해를 찾아가는 방법

그리디 알고리즘(Greedy Algorithm)은 현재 상황에서 가장 좋은 선택(예를들면 높은 수)만을 하는 알고리즘 기법입니다.

이 알고리즘은 문제를 해결하는 과정에서 매 순간 최적이라고 생각되는 결정을 내리며, 이 과정을 통해 전체적인 최적해를 찾아갑니다.

그리디 알고리즘은 단순하고 직관적이지만, 항상 최적해를 보장하지는 않습니다.

그러나 많은 문제에서 그리디 알고리즘은 효율적이고 효과적인 해결책을 제공합니다.

 

그리디 알고리즘의 특징

1. 단계적 선택: 문제를 해결하는 과정에서 매 단계마다 가장 최적의 선택을 합니다.
2. 지역적 최적해: 각 단계에서의 선택이 전체 문제의 최적해를 보장하지는 않지만, 각 단계에서의 최적 선택을 통해 전체 문제의 해결을 시도합니다.
3. 비가역적 선택: 한번 선택한 것은 다시 번복하지 않습니다. 즉, 이전 단계의 선택은 이후의 단계에 영향을 미치지 않습니다.

그리디 알고리즘의 장점

• 단순성: 그리디 알고리즘은 직관적이고 이해하기 쉬워서 구현이 간단합니다.
• 속도: 매 단계에서 최적의 선택을 하므로 계산 속도가 빠릅니다.
• 효율성: 많은 문제에서 그리디 알고리즘은 적절한 해를 빠르게 제공합니다.

그리디 알고리즘의 단점

• 최적해 보장 불가: 그리디 알고리즘은 항상 최적해를 보장하지 않습니다. 즉, 그리디 알고리즘으로 풀 수 없는 문제가 존재합니다.
• 문제 특성: 그리디 알고리즘이 최적해를 보장하려면 문제 자체가 그리디 특성을 가져야 합니다.

그리디 알고리즘의 적용 예시

1. 동전 거슬러주기 문제

가장 단순한 그리디 알고리즘의 예시로, 동전 거슬러주기 문제가 있습니다.

예를 들어, 500원, 100원, 50원, 10원의 동전이 있을 때, 주어진 금액을 최소 개수의 동전으로 거슬러주려면 어떻게 해야 할까요?

def coin_change(n, coins):
    count = 0
    for coin in coins:
        count += n // coin
        n %= coin
    return count

coins = [500, 100, 50, 10]
n = 1260
print(coin_change(n, coins))  # 출력: 6

 

2. 회의실 배정 문제

여러 개의 회의가 있을 때, 회의가 겹치지 않도록 하면서 최대한 많은 회의를 배정하는 문제입니다.

def max_meetings(meetings):
    meetings.sort(key=lambda x: x[1])  # 종료 시간을 기준으로 정렬
    end_time = 0
    count = 0

    for meeting in meetings:
        if meeting[0] >= end_time:
            end_time = meeting[1]
            count += 1

    return count

meetings = [(1, 4), (2, 3), (3, 5), (6, 7), (8, 9)]
print(max_meetings(meetings))  # 출력: 4

 

3. 배낭 문제

물건들을 배낭에 넣을 때, 물건들의 무게와 가치를 고려하여 배낭에 넣을 수 있는 가치의 합을 최대화하는 문제입니다.

def knapsack(items, max_weight):
    items.sort(key=lambda x: x[1] / x[0], reverse=True)  # 단위 무게당 가치로 정렬
    total_value = 0
    for weight, value in items:
        if max_weight >= weight:
            max_weight -= weight
            total_value += value
        else:
            total_value += value * (max_weight / weight)
            break
    return total_value

items = [(10, 60), (20, 100), (30, 120)]
max_weight = 50
print(knapsack(items, max_weight))  # 출력: 240.0

 

그리디 알고리즘의 활용

그리디 알고리즘은 다음과 같은 문제에서 자주 사용됩니다:

• 최단 경로 문제(다익스트라 알고리즘)
• 최소 신장 트리 문제(크루스칼 알고리즘, 프림 알고리즘)
• 작업 스케줄링 문제
• Huffman 코딩

 

결론

그리디 알고리즘은 단순하고 직관적인 방법으로 문제를 해결하는 강력한 도구입니다.

하지만 모든 문제에서 최적해를 보장하지 않으므로, 문제의 특성을 잘 파악하고 그리디 알고리즘이 적합한지 판단하는 것이 중요합니다.