グリーディ法（Greedy Algorithm）をやさしく解説｜一番よさそうな選択を積み重ねる考え方とは？

グリーディ法は、毎回その場で一番よさそうな選択をしていく方法です。シンプルで速いけれど、いつも正解とは限らない。このアルゴリズムの考え方と、実際にどう使われるのかを、専門用語をできるだけ使わずに小学生でもわかるように丁寧に解説します。

グリーディ法ってなに？

グリーディ法（Greedy Algorithm）は、とても単純で分かりやすい考え方の「問題を解く方法（アルゴリズム）」です。

どんな考え方かというと――

「そのとき、その場で、一番よさそうなものを選び続ける」

というルールだけで、ゴールまでたどり着こうとする方法です。

たとえば、お菓子を一番たくさんもらいたいとき、「目の前にある中で一番大きいお菓子をどんどん取っていく」というようなやり方です。

どうして“グリーディ”なの？

“Greedy（グリーディ）”とは英語で「欲ばりな」という意味です。

この方法では「もっと先を見ればいいものがあるかも…」ということは考えません。 とにかく目の前で一番よさそうなものをどんどん選んでいきます。

その場ではよさそうに見えるけど、本当に一番いい方法かどうかは分からない―― それがグリーディ法の特徴です。

どんなときに使える？

グリーディ法が向いているのは、次のような場面です。

• 全体を見なくても、部分ごとのベストが全体のベストにつながるとき
• とにかく速く答えを出したいとき
• 計算する時間やメモリをできるだけ減らしたいとき

でも逆に、

• 先のことを考えないといけない問題
• 少し遠回りしてでも良い結果を出したい問題

には向いていないことがあります。

例で学ぼう：おつりの計算

お店で500円払って、おつりをなるべく少ない枚数で返したいときの話を考えてみましょう。

使える硬貨は「100円」「50円」「10円」「5円」「1円」だったとします。

おつりが 137円 のとき、グリーディ法ではこう考えます：

1. 一番大きい100円玉 → 1枚（残り37円）
2. 次に大きい50円 → 無理（大きすぎる）
3. 次の10円 → 3枚（残り7円）
4. 次の5円 → 1枚（残り2円）
5. 次の1円 → 2枚（ちょうど！）

→ 合計：1枚 + 3枚 + 1枚 + 2枚 = 7枚

この方法はグリーディ法で正解です。 でも、もし変な硬貨の種類だったら、間違った答えになることもあります。

他にもこんな場面で使える

• 仕事のスケジュールを組むとき（締切が早い順にやる）
• 荷物をリュックに詰めるとき（重さのわりに価値が高いものから詰める）
• 電車の乗り換えを最小にしたいとき（次の駅で一番近い線に乗り換える）

など、現実でもけっこう使われている考え方です。

グリーディ法のいいところと注意点

でも…

まとめ

グリーディ法は、「目の前の一番いい選択」を積み重ねて、答えにたどりつく考え方です。

• シンプルで速いけれど、
• 本当に一番いい答えを出せるとは限らない。

だからこそ、使える場面を見きわめることが大事です。

「簡単だけど奥が深い」グリーディ法。 もしあなたが、何か問題をすばやく解決したいとき――この方法を思い出してみてください。