탐욕 알고리즘의 기본, 문제 풀이

그리디 알고리즘(Greedy Algorithm) 또는 탐욕 알고리즘은 매 단계에서 가장 최선이라고 생각되는 선택을 하여 전체 최적의 해를 구하는 알고리즘입니다. 그리디 알고리즘은 모든 경우를 고려하는 대신 현재의 선택에 집중하여 빠르고 효율적인 해결책을 제공합니다.

이 알고리즘은 특정 조건을 만족하는 문제에 적합하며, 대표적으로 최소 동전 개수 구하기와 최대 이익 얻기 문제에서 사용됩니다.

그리디 알고리즘은 매 단계에서 가장 최선의 선택을 반복적으로 수행하여 최적의 결과를 도출하려고 합니다. 이 알고리즘이 항상 최적의 해를 보장하는 것은 아니지만, 특정 조건을 만족하는 문제에서는 매우 효율적인 해법이 됩니다.

그리디 알고리즘을 적용할 수 있는 대표적인 조건은 다음과 같습니다:

• 탐욕적 선택 속성: 각 단계에서 최선의 선택을 했을 때, 그 선택이 전체 문제의 최적 해에 영향을 미치지 않는 경우입니다.
• 최적 부분 구조: 문제의 최적 해가 부분 문제의 최적 해로 구성될 수 있어야 합니다. 즉, 문제를 작은 문제로 나누어도 같은 방식으로 해결할 수 있어야 합니다.

그리디 알고리즘의 기본 개념은 탐색 과정에서 매 순간 가장 좋은 선택을 함으로써 문제를 해결하는 것입니다. 이 때문에 그리디 알고리즘은 모든 경우를 탐색하는 동적 계획법(Dynamic Programming)보다 일반적으로 더 빠릅니다.

다음 예제는 가장 적은 동전 개수로 특정 금액을 만드는 문제입니다. 각 동전의 단위가 주어졌을 때, 최소 동전 개수로 목표 금액을 만들기 위해 그리디 알고리즘을 사용할 수 있습니다.

Python 코드 예제:
def min_coins(target, coins):
    coins.sort(reverse=True)  # 큰 단위의 동전부터 사용하기 위해 내림차순 정렬
    count = 0

    for coin in coins:
        # 현재 동전으로 만들 수 있는 최대 개수를 계산
        if target >= coin:
            count += target // coin
            target %= coin  # 남은 금액 계산

    return count

# 예제 사용
target = 760
coins = [500, 100, 50, 10]
print(min_coins(target, coins))  # 출력: 4 (500 + 100 + 100 + 50 + 10)
                

설명: min_coins 함수는 가장 큰 단위의 동전부터 사용하여 목표 금액을 만드는 방식입니다. 큰 단위의 동전을 우선 사용함으로써 최적의 동전 개수를 빠르게 구할 수 있습니다.

그리디 알고리즘은 다양한 문제에서 활용할 수 있습니다. 특히 최대화 혹은 최소화 문제에 자주 사용되며, 특정 조건에서 최적의 해를 보장합니다. 다음은 그리디 알고리즘을 사용하여 해결할 수 있는 몇 가지 문제 예제입니다.

예제 1: 최대 이익을 얻기 위한 작업 스케줄링

여러 작업이 각각 시작 시간과 종료 시간을 가질 때, 겹치지 않게 최대한 많은 작업을 수행하는 문제는 그리디 알고리즘으로 해결할 수 있습니다. 이 문제에서는 종료 시간이 빠른 순서대로 작업을 선택하는 방식이 최적의 해를 보장합니다.

Python 코드 예제:
def max_jobs(jobs):
    jobs.sort(key=lambda x: x[1])  # 종료 시간이 빠른 순으로 정렬
    count, last_end = 0, 0

    for start, end in jobs:
        # 현재 작업의 시작 시간이 마지막 작업의 종료 시간 이후라면 선택
        if start >= last_end:
            count += 1
            last_end = end

    return count

# 예제 사용
jobs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(max_jobs(jobs))  # 출력: 4 (최대 수행 가능한 작업 수)
                

설명: max_jobs 함수는 작업 리스트를 종료 시간 기준으로 정렬한 후, 겹치지 않게 최대한 많은 작업을 선택합니다. 종료 시간이 빠른 작업부터 선택하면, 더 많은 작업을 할 수 있는 기회가 늘어납니다.

예제 2: 배낭 문제(0-1 Knapsack Problem)

그리디 알고리즘은 각 물건의 가치를 무게로 나눈 값을 기준으로 물건을 선택함으로써 배낭 문제를 풀 수 있습니다. 이 방법은 물건을 쪼개서 넣을 수 있는 경우에 적용할 수 있습니다.

Python 코드 예제:
def fractional_knapsack(items, capacity):
    # 무게 대비 가치가 높은 순으로 정렬
    items.sort(key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0

    for weight, value in items:
        if capacity >= weight:
            # 물건을 전부 넣을 수 있는 경우
            total_value += value
            capacity -= weight
        else:
            # 물건을 일부만 넣을 수 있는 경우
            total_value += (value / weight) * capacity
            break

    return total_value

# 예제 사용
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
print(fractional_knapsack(items, capacity))  # 출력: 240.0
                

설명: fractional_knapsack 함수는 무게 대비 가치가 높은 물건부터 배낭에 담아 최대 가치를 구합니다. 배낭의 용량이 부족할 경우 일부만 넣어 최적의 해를 구할 수 있습니다.

그리디 알고리즘은 단순하고 빠르며, 대부분의 경우 $$O(N)$$ 또는 $$O(N \log N)$$의 시간 복잡도를 가집니다. 그러나 항상 최적의 해를 보장하지는 않기 때문에, 문제에 대한 철저한 분석이 필요합니다.

장점

• 탐색 과정이 단순하여 빠르고 효율적인 문제 해결이 가능합니다.
• 다양한 최적화 문제에서 $$O(N)$$ 또는 $$O(N \log N)$$의 효율적인 시간 복잡도를 제공합니다.

한계

• 그리디 알고리즘이 항상 최적의 해를 보장하지 않기 때문에 최적 부분 구조가 성립해야 적용이 가능합니다.
• 복잡한 문제에 대해 다항 시간 복잡도의 해법이 필요할 경우에는 그리디 알고리즘이 적합하지 않을 수 있습니다.

따라서, 그리디 알고리즘이 적합한지 판단하는 기준을 잘 이해하고 분석할 필요가 있습니다.