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

2024-10-29 16:11:27 | 조회수 90


그리디 알고리즘: 탐욕 알고리즘의 기본과 다양한 문제 풀이

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

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

1. 그리디 알고리즘의 기본 원리

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

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

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

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

2. 그리디 알고리즘 예제: 최소 동전 개수 문제

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

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 함수는 가장 큰 단위의 동전부터 사용하여 목표 금액을 만드는 방식입니다. 큰 단위의 동전을 우선 사용함으로써 최적의 동전 개수를 빠르게 구할 수 있습니다.

3. 그리디 알고리즘의 다양한 응용 사례

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

예제 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 함수는 무게 대비 가치가 높은 물건부터 배낭에 담아 최대 가치를 구합니다. 배낭의 용량이 부족할 경우 일부만 넣어 최적의 해를 구할 수 있습니다.

4. 그리디 알고리즘의 장점과 한계

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

장점

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

한계

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

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

이번 글에서는 그리디 알고리즘의 기본 개념과 다양한 문제 예제를 학습했습니다. 탐욕적 선택 속성과 최적 부분 구조를 이해하고, 다양한 실전 문제에 응용하여 그리디 알고리즘의 장점을 활용해 보세요.


탐욕 알고리즘의 기본, 문제 풀이 - 알고리즘닷컴 19 개의 글