【アルゴリズム】その場その場の最良を選んで突き進む！「貪欲法」｜情報処理問題1000本ノック
迷路を解くとき、全体のマップを見ずに「とりあえず今、一番ゴールに近づけそうな道」を毎回選んで進む手法があります。このように、各ステップでその時点で最適なものを選び続けるアルゴリズムの設計手法「貪欲法（グリーディアルゴリズム）」を攻略しましょう。
1. 【 問題 】：アルゴリズムの設計手法（貪欲法）
【 問題 】 最適化問題を解くためのアルゴリズムの設計手法のうち、将来の計画や全体の影響を考慮せず、各ステップにおいて「その時点で最も有利（最良）」と判断される選択を繰り返すことで、最終的な解に到達しようとする手法を何と呼ぶでしょうか？
① 動的計画法（ダイナミック プログラミング）
② 貪欲法（グリーディアルゴリズム）
③ 分割統治法（ディバイド アンド コンカー）
④ 全探索法（ブルートフォースアタック）
2. 正解：
正解： ② 貪欲法（グリーディアルゴリズム）
3. 解説：遠い将来より「いま目の前のトク」を優先する
貪欲法（どんよくほう）は、問題をいくつかのステップに分割し、それぞれの段階で「局所的な最適解」を貪欲（グリーディ）に選び続ける手法です。計算量が非常に少なく、素早くそれなりの解（近似解）を導き出せるのが大きなメリットです。ただし、目先の最良を選び続けた結果、最終的な合計（全体最適）がベストになるとは限らないという弱点もあります。
| 手法名 | アプローチの特徴 | 代表的な応用例 |
|---|---|---|
| ① 動的計画法 | 問題を小さな部分問題に分け、計算結果を記録して再利用する | ナップサック問題、最長共通部分列 |
| ② 貪欲法 | 各ステップで「その時点で最良」な選択を繰り返す | お釣りの硬貨枚数の最小化、ダイクストラ法 |
| ③ 分割統治法 | 問題を小さく分解してそれぞれを解き、最後に組み合わせる | マージソート、クイックソート |
| ④ 全探索法 | 可能性のあるすべてのパターンを力任せに調べる | パスワードの総当たり、暗号解読 |
1. 理解のコツ: 「レジでお釣りを渡すときの硬貨の選び方」を想像してください。
480円のお釣りを渡すとき、私たちは無意識に「その時点で使える一番大きな硬貨」を貪欲に選びます。
・まず、480円以下で最大の「500円」は使えないので、次に大きい「100円」を4枚選びます（残り80円）。
・残り80円から、最大の「500円」「100円」は無理なので「50円」を1枚選びます（残り30円）。
・残り30円から、「10円」を3枚選びます（残り0円）。
これで合計8枚という「最も枚数が少ない正しい組み合わせ」に一発でたどり着けます。このように、日本の硬貨（500, 100, 50, 10, 5, 1）のような絶妙なバランスのシステムでは、貪欲法で常に100点満点の正解（最適解）が出せます。
しかし、もし「1円、4円、6円」という特殊な硬貨しかない国で「8円」のお釣りを作る場合、貪欲法だと「まず最大の6円を1枚、残りは1円を2枚」で合計3枚になりますが、本当の正解は「4円を2枚」の合計2枚です。このように、条件によっては100点満点にならないこともあるのが貪欲法の特徴です。
2. 試験対策の視点: 午前試験では、「その時点で最良のものを〜」というフレーズが出たら確実に貪欲法（または決定論的アプローチ、ヒューリスティック）を選びましょう。また、ネットワークの最短経路を求める「ダイクストラ法」や、最小全域木を求める「プリム法」「クラスカル法」のベースになっている思想もこの貪欲法です。午後試験では、アルゴリズムの穴埋め問題として「今一番コストが小さい要素をソートして取り出す処理」などを選ばせる形でよく登場します。
4. まとめ
「将来への影響は一切考えず、各ステップにおいてその時点で最も有利な選択を積み重ねて解を導く手法」。これが貪欲法です。完ペキな正解（最適解）にならないこともあるけれど、とにかく早くてシンプルな答えが出せる実用的なアルゴリズムとして覚えておきましょう！