【アルゴリズム設計】その場その場の「ベスト」を愚直に選ぶ！「貪欲法（Greedy Algorithm）」｜情報処理問題1000本ノック
基本情報技術者試験、応用情報技術者試験、アルゴリズム・プログラミング分野で頻出の重要設計手法。「貪欲法（グリーディ法）」の定義と、動的計画法（DP）や全探索との違いを攻略しましょう。
1. 【 問題 】：テクノロジ系（アルゴリズム・データ構造）
【 問題 】 段階的に判断を行う最適化問題のアルゴリズム設計技法に関する記述です。各ステップにおいて、全体最適解になるかどうかの検証や将来への影響の考慮を行わず、その時点で最も評価が高い選択肢（局所最適解）を貪欲に選び続けて解を導出する手法は、次のうちどれか。
（ア）動的計画法（Dynamic Programming）
（イ）貪欲法（Greedy Algorithm）
（ウ）分割統治法（Divide and Conquer）
（エ）バックトラッキング（Backtracking）
2. 正解：
正解：（イ）貪欲法（Greedy Algorithm）
3. 解説：「『目先の利益』を最優先で選んで進むシンプル解法！」
貪欲法（Greedy Algorithm）は、「目先の利益（局所解）」だけを見て選択を決定していく手法です。
計算量が少なく高速に解を求められるメリットがある反面、「全体の最適解（全体解）」に到達できるかどうかは問題の構造（マトロイド構造や最適な部分構造をもつか）に依存するという性質があります。
| 設計技法 | アプローチの特徴 | 代表的な適用例 |
|---|---|---|
| （イ）貪欲法 （Greedy） |
各ステップで目先の局所最適解を検証せずに選択する。高速。 | おつりの枚数最小化（日本円等の硬貨）、ハフマン符号、プリム法・ダイクストラ法（グラフ最短経路） |
| （ア）動的計画法 （DP） |
問題を小さな部分問題に分割し、部分問題の計算結果をメモ（記録）して再利用することで全体最適解を求める。 | ナップサック問題、編集距離（Levenshtein distance） |
| （ウ）分割統治法 | 大きな問題を小さく分割し、それぞれを独立して解いたあとに解を結合・統合する。 | マージソルト、クイックソート |
| （エ）バックトラッキング | 解の候補を探索し、条件に合わないと分かった時点で1つ前の分岐まで戻って別の選択肢を試す（枝刈り）。 | Nクイーン問題、迷路解法 |
1. 理解のコツ:
・例えば「100円、50円、10円、1円で462円のおつりを払う」時、「大きい硬貨から順番に使えるだけ使う」という選び方は貪欲法です（日本円の貨幣体系では、この貪欲法で枚数最小＝全体最適解になります）。
・一方、特殊な硬貨体系（例：1円、4円、5円で8円を作る場合、貪欲法だと `5+1+1+1` で4枚になりますが、全体最適解は `4+4` の2枚）では、貪欲法では最適解にならないケースがあります。
2. 試験対策の視点:
・問題文に「局所解」「全体最適解であるか検証しない」「その時点で最も良い選択肢を選ぶ」「目先の最適」と来たら、迷わず貪欲法（グリーディ法）を選択しましょう！
4. まとめ
検証を行わずに各段階の局所最適解（目先の最善）を選択していくアルゴリズム設計手法。これが貪欲法です。部分問題の計算結果をメモしながら全体最適を保証する「動的計画法（DP）」との違いも含めてしっかり整理しておきましょう！