탐욕 알고리즘(Greedy Algorithm)은 최적해를 구하기 위해 매 순간 가장 최적인 선택을 하는 알고리즘입니다. 이 알고리즘은 각 단계에서의 선택이 전체적으로 최적이라고 가정하고 문제를 해결합니다.

탐욕 알고리즘의 예시

다음은 탐욕 알고리즘의 예시입니다. 카드를 이용한 최대 합 게임을 해결하는 알고리즘입니다.

1. 입력으로 주어진 카드의 숫자들 중 가장 큰 숫자를 선택합니다.
2. 선택한 카드를 제외한 나머지 카드 중 가장 큰 숫자를 선택합니다.
3. 선택한 카드를 제외한 나머지 카드 중 가장 큰 숫자를 선택합니다.
4. 이를 반복적으로 수행하여 선택한 카드들의 숫자를 합산합니다.

이 알고리즘은 각 단계에서 가장 큰 숫자를 선택하기 때문에, 전체적으로 합이 최대가 되는 카드들을 선택할 수 있습니다.

def greedy_max_sum(cards):
    card_sum = 0
    
    while len(cards) > 0:
        max_card = max(cards)
        card_sum += max_card
        cards.remove(max_card)
    
    return card_sum

cards = [3, 5, 2, 9, 8, 10, 1, 4]
max_sum = greedy_max_sum(cards)
print(max_sum) # 출력 결과: 42

위의 코드는 주어진 카드 리스트에서 탐욕 알고리즘을 이용하여 최대 합을 구하는 예시입니다. 입력으로 주어지는 카드의 숫자 리스트에서 가장 큰 숫자를 선택하고, 선택한 숫자를 리스트에서 제거하는 과정을 반복하여 최대 합을 계산합니다.

탐욕 알고리즘의 한계점

탐욕 알고리즘은 각 단계에서의 선택이 최적이라고 가정하기 때문에, 항상 최적해를 구할 수 있는 것은 아닙니다. 때로는 지역 최적해에 빠져서 전체적으로는 최적해를 구하지 못할 수도 있습니다. 따라서, 탐욕 알고리즘을 사용할 때에는 문제의 특성을 잘 파악하고 적용해야 합니다.

참고 자료

• Greedy Algorithm - Wikipedia
• 탐욕 알고리즘 - GeeksforGeeks