Algorithm/Greedy

[Algorithm] 그리디(탐욕) 알고리즘 - 파이썬

그리디(탐욕) 알고리즘 - 파이썬

그리디 알고리즘(혹은 탐욕 알고리즘)은 각 단계에서 지금 당장 가장 좋은 선택을 하는 최적화 알고리즘이다. 즉, 각 단계에서 한 번 결정이 이루어지면 이를 번복하지 않고 최종적인 해답을 찾아내는 방법이다. 이 알고리즘은 각 선택의 결과가 다음 선택에 영향을 미치지 않을 때 특히 효과적이다. 또한 그리디 알고리즘은 전체 문제에 대한 최적해를 구하기 위해 각 단계에서 지역적으로 최적해를 선택하는 방법을 사용한다.

일상생활에서의 그리디 알고리즘

가방에는 정해진 무게까지만 물건을 담을 수 있다고 가정해보자. 여러 가지 물건이 있고 각 물건은 가치와 무게를 가지고 있다. 당신은 이 가방에 물건을 담아서 최대한 가치를 높여야 된다고 생각해보자.

여기서 그리디 알고리즘을 적용할 수 있다. 그리디 알고리즘에 따르면, 각 단계에서 현재 시점에서 가장 가치가 높은 물건을 선택하여 가방에 담는 것이 최적의 선택이다 .이를 통해 쇼핑 가방을 효율적으로 활용하여 가장 큰 가치의 물건을 선택하는 것이 목표이다.

예를 들어, 여러 종류의 과자가 있을 때, 그리디 알고리즘을 사용하면 현재 시점에서 가장 비싼 과자를 선택하여 가방에 담는 것이 최적의 선택이 될 수 있다. 이렇게 선택된 과자들로 인해 전체적인 쇼핑 가방의 가치를 최대한 높이는 것이 목표이다.

그리디 알고리즘의 정당성

그리디 알고리즘은 매 순간마다 가장 최적인 선택을 하는 방식으로 동작한다고 설명하였다. 이를테면, 그리디 알고리즘이 문제의 처직해를 찾기 위해 각 단계에서 지금 당장 가장 좋은 선택을 하는 방법이다. 그러나 이러한 각 단계에서의 최적해들이 모여서 전체적인 문제의 최적해를 이루는걸 보장하지는 않는다.

그리디 알고리즘의 정당성을 설명하는 핵심 아이디어는 "국소 최적해가 전역 최적해를 보장한다"이다. 다시 말해 각 단계에서의 최적한 선택이 전체적인 문제의 처적해에 도달하는데 충분하다는 것이다. 그리디 알고리즘의 정당성을 입증하려면 아래의 두 가지 핵심을 고려해야 한다.

탐욕 선택 속성(Greedy Choice Property) - 현재 상태에서 가장 최적인 선택을 한다.
최적 부분 구조(Optimal Substructure) - 전체 문제의 최적해가 부분 문제의 최적해로부터 구성될 수 있다.

그리디 알고리즘이 위의 두 가지 속성을 만족한다면, 해당 알고리즘은 정당하다고 할 수 있다. 하지만 모든 문제에 그리디 알고리즘을 적용할 수 있는 것은 아니며, 각 문제에 따라 적절한 정당성 증명이 필요하다. 일부 문제에서는 동적 계획법(Dynamic Programming)이나 다른 최적화 기법이 더 적절할 수 있다.

파이썬으로 구현하는 그리디 알고리즘

그리디 알고리즘을 파이썬으로 구현하는 것은 각 문제에 따라 다르지만, 그리디 알고리즘의 일반적인 흐름을 보여주는 간단한 예제를 한 번 살펴보자. 여기서는 거스름돈 문제와 회의실 배정 문제를 예로 들어보겠다.

거스름돈 문제

어떤 가게에서 물건을 사고자 할 때, 지불해야 할 돈과 상품의 가격이 주어진다. 이때, 거스름돈을 가장 적은 동전의 개수로 주려면 어떻게 해야할까?

def greedy_change(money, coins):
    change = []  # 거스름돈 동전들을 담을 리스트

    # 동전의 큰 단위부터 차례대로 확인
    for coin in sorted(coins, reverse = True):
        while money >= coin:  # 현재 동전을 거슬러 줄 수 있을 때까지 반복
            money -= coin
            change.append(coin)

    return change

# 예시
money = 1260
coins = [500, 100, 50, 10]
result = greedy_change(money, coins)
print(result)

위의 예제에서는 가장 큰 동전부터 시작하여 현재 동전으로 거슬러 줄 수 있는 만큼 거슬러 주고, 다음으로 가장 작은 동전부터 넘어가는 방식이다. 여기서 중요한 것은 가장 큰 동전부터 시작해야한다는 점이다. 이것이 그리디 알고리즘의 전형적인 흐름 중 하나이다.

[500, 500, 100, 100, 50, 10]

실행 결과

회의실 배정 문제

또 다른 간단한 그리디 알고리즘 예제로는 회의실 배정 문제를 살펴보자. 이 문제에서는 여러 회의가 겹치지 않게 최대한 많이 진행되도록 회의를 선택하는 문제이다.

def activity_selection(activities):
    sorted_activities = sorted(activities, key = lambda x : x[1])  # 끝나는 시간을 기준으로 정렬
    print(f"정렬 후 : {sorted_activities}")

    selected_activities = []

    last_end_time = 0

    for activity in sorted_activities:
        start_time, end_time = activity
        if start_time >= last_end_time:
            selected_activities.append(activity)
            last_end_time = end_time

    return selected_activities

# 예시
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
result = activity_selection(activities)
print(f"정답 : {result}")

위 예제에서는 회의의 시작 시간과 끝나는 시간이 주어질 때, 겹치지 않게 최대한 많은 회의를 선택하는 문제이다. 끝나는 시간을 기준으로 정렬하고, 현재까지 선택한 회의의 끝나는 시간을 유지하면서 가능한 많은 회의를 선택한다. 이 역시 그리디 알고리즘의 전형적인 예제 중 하나이다.

정렬 후 : [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
정답 : [(1, 4), (5, 7), (8, 9)]

실행 결과

그리디 알고리즘은 간단하고 직관적이며 빠른 실행 속도를 가지는 특성이 있다. 그러나 항상 최적 해를 구할 수 있는 것은 아니며, 문제의 특성에 따라 다양한 경우가 있다. 따라서 사용 가능 여부를 판단하기 위해 최적 부분 구조와 탐욕적 선택 속성을 확인하는 것이 중요하다.

728x90

Contents

새소식

인기 검색어