貪欲法: 今いちばんよい選択を積み重ねよう

貪欲法は、その時点で一番よさそうな選択をくり返す方法です。

おつりを出すときに、大きい硬貨から使うような考え方です。

使いどころ

• 硬貨の枚数を減らす
• 締切がある作業を選ぶ
• 区間をできるだけ多く選ぶ
• 毎回の最善が全体の最善につながる問題

手順

1. 候補を見比べる
2. 今一番よいものを選ぶ
3. 選んだ結果を反映する
4. 次の候補で同じことをくり返す

図で見る

コピペ用コード

coins = [100, 50, 10, 1]
amount = 186
count = 0

for coin in coins:
    count += amount // coin
    amount %= coin

print(count)

コードの読み方

• coins は大きい順に並んでいます。
• amount // coin で、その硬貨を何枚使えるか計算します。
• amount %= coin で、残りの金額に更新します。

別パターン1: 締切つきの仕事を選ぶ（区間スケジューリング）

「終わる時間が早い仕事から選ぶ」という貪欲法で、できるだけ多くの仕事を引き受ける例です。

# (開始時刻, 終了時刻) のリスト
jobs = [(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)]

# 終了時刻が早い順に並べ替える
jobs.sort(key=lambda job: job[1])

count = 0
current_end = 0

for start, end in jobs:
    if start >= current_end:
        count += 1
        current_end = end

print(count)  # 3

• jobs.sort(key=lambda job: job[1]) で、終了時刻の早い順に並べます。この並べ替えが貪欲法の「選ぶ基準」です。
• start >= current_end は、「前の仕事が終わってから始められるか」の確認です。
• 早く終わる仕事を選ぶほど、後の時間が空くので、選べる本数が最大になります。

別パターン2: おつりの枚数を辞書で数える

最初の例を発展させて、「どの硬貨を何枚使ったか」まで記録するパターンです。

coins = [500, 100, 50, 10, 5, 1]
amount = 738
used = {}

for coin in coins:
    used[coin] = amount // coin
    amount %= coin

for coin, count in used.items():
    if count > 0:
        print(f"{coin}円玉 × {count}枚")

• used という辞書に「硬貨 → 枚数」を記録しています。
• 日本の硬貨のように「大きい硬貨が小さい硬貨の倍数関係になっている」場合、この貪欲法で必ず最少枚数になります。

貪欲法が失敗する例

貪欲法は万能ではありません。たとえば硬貨が [4, 3, 1] で 6 を支払う場合を考えます。

coins = [4, 3, 1]
amount = 6
count = 0

for coin in coins:
    count += amount // coin
    amount %= coin

print(count)  # 3 (4円+1円+1円) だが、正解は 2 (3円+3円)

「今一番大きい 4 を選ぶ」ことが、全体の最善につながっていません。このような場合は動的計画法を使います。

計算量

貪欲法そのものの計算量は、多くの場合「並べ替え O(n log n) ＋ 1回のループ O(n)」で O(n log n) です。全パターンを試す方法に比べて圧倒的に高速なのが強みです。

よくあるミス

ミス	何が起きるか	対処
貪欲法が使えない問題に使う	一見動くが答えが間違う	「今の最善＝全体の最善」の理由を説明できるか確認する
選ぶ基準（ソート順）を間違える	最適でない答えになる	「何を基準に選ぶと得か」を小さい例で検証する
小さい例で確認しない	提出・公開後に間違いに気づく	手計算できるサイズで答え合わせする

注意点

貪欲法はいつでも正しいとは限りません。「今の最善」が「全体の最善」になる理由を説明できるときに使います。迷ったら、小さい入力で全パターンを試すコードを書き、貪欲法の答えと一致するか確かめるのが確実です。