貪欲法 — Greedy Algorithm

このトピックを修了すると

貪欲法がどのように機能するかを理解し、いつ適用できるかを判断し、代表的な問題を自分で解くことができるようになります。

主要なアイデア

コンビニエンスストアで1,260ウォンのお釣りを渡す必要があります。コインは500ウォン、100ウォン、50ウォン、10ウォンです。

直感的な方法: 最も大きいコインからできるだけ多く使います。

def coin_change(amount):
    coins = [500, 100, 50, 10]
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

print(coin_change(1260))  # 6個 (500×2 + 100×2 + 50×1 + 10×1)

各ステップで、現在、最善の選択を行います。過去を振り返らず、未来を見据えません。これが貪欲法（Greedy Algorithm）です。

なぜ「貪欲」なのか

貪欲法の特徴：

1. 局所最適（local optimum）: 現在の時点で最も良い選択
2. 後戻りなし: 一度選択したら、それを覆さない
3. 全体最適（global optimum）を保証する条件: 特定の条件が満たされる場合にのみ、全体的な最適解となる

お釣りの問題で、まず500ウォンのコインを使うことは直感的に正しいです。しかし、すべての問題でこの戦略が通用するわけではありません。

貪欲法が通用する条件

貪欲法で最適解が保証されるためには、次の2つの性質が必要です。

貪欲選択性（Greedy Choice Property）

各ステップでの最善の選択は、全体の最適解に含まれます。

お釣りの例：500ウォンのコインをできるだけ多く使うことが、常に最適解に含まれます。なぜなら、500ウォン = 100ウォン × 5であるため、500ウォンを使わないと、コインの数が必ず増えるからです。

最適部分構造（Optimal Substructure）

大きな問題の最適解は、部分問題の最適解を含みます。

1260ウォンの最適解 = 500ウォン2個の選択 + "260ウォンの最適解"。残りの260ウォンも、同じ戦略で解くことができます。

貪欲法が失敗する場合

コインが[400, 300, 100]ウォンで、600ウォンのお釣りを渡す必要がある場合：

# 貪欲法: 400 + 100 + 100 = 3個
# 最適解: 300 + 300 = 2個

最初に400ウォンを選択すると、残りの200ウォンを100ウォン2枚で支払う必要があります。しかし、300ウォン2枚の方が少なくなります。大きいコインから使うという戦略が失敗します。

この場合、500、100、50、10のように、大きいコインが小さいコインの整数の倍数ではないためです。倍数の関係が崩れると、貪欲法は最適解を保証しません。このような問題には、動的計画法（DP）が必要です。

代表的な問題1：活動選択（Activity Selection）

会議室が1つあり、複数の会議のリクエストがあります。重ならないように、できるだけ多くの会議をスケジュールするには？

def max_meetings(meetings):
    # 終了時間に基づいてソート
    meetings.sort(key=lambda m: m[1])

    count = 0
    last_end = 0
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))  # 4個

貪欲戦略: 終了時間が最も早い会議から選択します。

なぜこれが最適なのか：早く終わる会議を選択することで、残りの時間が増え、より多くの会議をスケジュールできます。この問題は、貪欲選択性が数学的に証明されています。

代表的な問題2：分割可能なナップサック（Fractional Knapsack）

ナップサックの容量が50kgで、物を分割して入れることができる場合、価値を最大化するには：

def fractional_knapsack(capacity, items):
    # 重さあたりの価値に基づいて降順にソート
    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 * (capacity / weight)
            break
    return total_value

items = [(10, 60), (20, 100), (30, 120)]  # (重さ、価値)
print(fractional_knapsack(50, items))  # 240.0

貪欲戦略: 重さあたりの価値（コストパフォーマンス）が高いものから入れます。

注意：物を分割できない0-1ナップサック問題では、貪欲法は最適解を保証しません。0-1ナップサックは、DPで解く必要があります。

貪欲法 vs 完全探索 vs DP

貪欲法は高速ですが、条件が一致する場合にのみ正解です。条件が一致しない場合は、DPまたは完全探索を使用する必要があります。

コーディングテストでの判断方法

1. 「最も〜なものから選択すれば良さそうだ」→ 貪欲の候補
2. 反例を作成する → 反例がない場合は貪欲を適用
3. ソート基準が明確である → 貪欲の可能性が高い
4. 「残りの部分も同じように解くことができる」→ 最適部分構造の充足

貪欲法が疑わしい場合は、小さな入力で最初に反例を見つけてください。反例が見つかった場合は、DPに切り替えます。実際の貪欲問題では、ソートが重要な場合がほとんどです。

重要なポイント: 貪欲法は、「各瞬間、最善の選択をすれば、全体として最善の結果になる」という戦略です。お釣りの問題のように、条件が一致する場合はO(n)で解けますが、条件が一致しない場合は不正解になります。