2026.10.02

記事内に商品プロモーションを含む場合があります

貪欲法とは？ Pythonによるコード例

Aru

アルゴリズムとして貪欲法というのものがあります。貪欲法は、各ステップでその時点の最善を選んで後戻りしないアルゴリズムです。この記事では、貪欲法の考え方と、使える問題が持つ性質を整理します。具体例として「お金の支払い方（硬貨の枚数を最小にする）」問題を Python で実装し、日本の硬貨では正しく解ける一方、硬貨の組み合わせによっては失敗する例も確認します。

Contents

はじめに
貪欲法とは
- 定義
- 貪欲法の特徴
貪欲法が使える問題の性質
問題例（支払い方）
貪欲法が失敗する例
- なぜ解けない問題があるのか
まとめ

はじめに

アルゴリズムの学習を進めると「貪欲法（greedy algorithm）」という言葉をよく見かけます。考え方はとても素直でコードも短く書けます。一方で、使えるかどうかを見極めれないと、正しく動かない問題で使ってしまい誤った答えを出すことになります。

この記事では、貪欲法とは何か、どういう場面で使えるのかを整理します。

また、具体例として「お金の支払い方（硬貨の枚数を最小にする）」問題をPythonで解いてみます。

リンク

貪欲法とは

定義

貪欲法とは、問題を小さな選択の連続に分け、各ステップでその時点で最も良い選択だけをして、後戻りしないアルゴリズムです。

貪欲法（greedy algorithm）とは
各ステップで局所的に最適な選択を選び、それを積み重ねて解を組み立てる手法です。

たとえば硬貨枚数を最小化する問題なら「大きい額の硬貨から順に、使えるだけ使う」というのが貪欲法です。これは、人間がお釣りを考えるときの自然な考え方に近いものになります。

貪欲法の特徴

実装が簡単
ループ1つで書けることが多く、コードが短くなります
速い
後戻りしないため、全探索や動的計画法（DP）より計算量が小さくなる傾向があります
常に正しいとは限らない
局所的な最善を積み重ねても、全体の最善にならない場合があります。

貪欲法は「証明が難しい」ことでも知られています。実装は一瞬でも、本当に正しいかを示すのに手間がかかります。要注意です。

貪欲法が使える問題の性質

貪欲法が正しく動くには、次の2つの性質が必要と言われています。

1. 貪欲選択性（greedy choice property）

その場での最善の選択が、全体の最適解の一部になっているという性質です。

硬貨問題でいうと「いちばん大きい硬貨をできるだけ使う」という選択が、最適解に含まれている必要があります。もし大きい硬貨を多く使うと損をする問題なら、貪欲法は失敗します。

2. 最適部分構造（optimal substructure）

問題の最適解が、その部分問題の最適解から組み立てられるという性質です。

硬貨問題で 1234 円を払うとき、まず 1000 円硬貨を1枚使うと、残りは「234 円を最小枚数で払う」という一回り小さい同じ問題になります。このように、選択したあとに同じ形の部分問題が残るのがポイントです。

使える問題のまとめ

結論

「最善を選んでも損をしない（貪欲選択性）」かつ「選んだ後に同じ形の部分問題が残る（最適部分構造）」なら貪欲法が使える可能性が高い。

ただし、この2つを実際に証明するのは簡単ではありません。直感的には正解に思えても、いざ証明するのは難しい気がします。

問題例（支払い方）

支払い方の問題

ここからは具体例として、次の問題を考えます。

問題

1円、5円、10円、50円、100円、500円、1000円の硬貨（お札）がある。X円を支払うとき、使う硬貨の枚数を最小にせよ。

たとえば 1234 円を払うとき、どう組み合わせれば枚数が最少になるかを求める問題です。

問題の性質

この問題は、大きい額の硬貨から順番に、使えるだけ使うという貪欲法で解けます。

理由を直感的に説明すると、1枚の大きい硬貨は小さい硬貨何枚分もの価値があります。1000円札1枚と100円硬貨10枚は同じ1000円ですが、枚数は1枚と10枚です。そのため、大きい額を優先して使うほど枚数が少なくなりやすいわけです。

「大きい額から使えば最少になる」は、日本の硬貨だから成り立つ性質です。硬貨の種類が変わると、この直感は通用しません。詳しくは後の「貪欲法が失敗する例」で確認します。

Pythonでの実装例

まず、貪欲法で枚数を求めるコードです。コピペでそのまま動きます。

def min_coins_greedy(amount: int, coins: list[int]) -> int:
    """大きい硬貨から順に使って、最小枚数を求める（貪欲法）"""
    count = 0
    for coin in sorted(coins, reverse=True):  # 大きい順に並べる
        count += amount // coin               # その硬貨で払える枚数
        amount %= coin                        # 残りの金額
    return count


coins = [1, 5, 10, 50, 100, 500, 1000]
print(min_coins_greedy(1234, coins))  # 10

やっていることは単純で、硬貨を大きい順に見て amount // coin で枚数を足し、amount %= coin で残額に更新しているだけです。

実行結果は次のようになります。

1234 円の内訳は 1000円×1、100円×2、10円×3、1円×4 で、合計 10枚です。

DPでも同じ答えになるか確認する

貪欲法が本当に最少枚数になっているか、動的計画法（DP）で確認してみます。

def min_coins_dp(amount: int, coins: list[int]) -> int:
    """DPで最小枚数を求める（硬貨の種類を問わず正しい）"""
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount]


coins = [1, 5, 10, 50, 100, 500, 1000]
print(min_coins_dp(1234, coins))  # 10

DP は全パターンを網羅するので、こちらは日本の硬貨でなくても正しく解けます。

実行すると 10 となり、貪欲法と DP の答えが一致します。

日本の硬貨では貪欲法が正しく動くことが確認できます。

貪欲法が失敗する例

ここが貪欲法で最も注意すべき点です。硬貨の種類によっては、大きい額から使う貪欲法が最少枚数にならないことがあります。

たとえば硬貨が 1円、3円、4円のとき、6円を払うことを考えます。

貪欲法: 4円→1円→1円の 3枚
最適解: 3円→3円の 2枚

coins = [1, 3, 4]
print(min_coins_greedy(6, coins))  # 3（貪欲法は失敗）
print(min_coins_dp(6, coins))      # 2（DPは正しい）

このように、4円硬貨を優先してしまうと、後の残り（2円）を1円硬貨でしか払えず、結果的に枚数が増えてしまいます。

貪欲法で解く前に「大きい額を優先してよい硬貨の体系か」を確認する。日本の硬貨（1,5,10,50,100,500,1000）は貪欲法で正しく解けると言われていますが、任意の硬貨の組み合わせで成り立つわけではありません。

なぜ解けない問題があるのか

貪欲法で解けるかどうかは、硬貨の組み合わせで決まります。

貪欲法が使える十分条件（倍数ルール）

すべての硬貨が「その1つ下の硬貨の倍数」になっていれば、大きい硬貨から使う貪欲法で最少枚数が求まります。円はこれを満たしています（5は1の倍数、10は5の倍数、50は10の倍数、100は50の倍数、500は100の倍数、1000は500の倍数）。小さい硬貨が大きい硬貨1枚分たまったら、いつでも大きい硬貨にまとめて枚数を減らせるので、大きい硬貨から使うほど得になるからです。

1,3,4 は3が4の倍数でないため、このルールに当てはまりません。6円で失敗するのはそのためです。