【どんよくほう】
貪欲法（グリーディアルゴリズム） とは？
💡 「今一番いいもの」を選び続ける
📌 このページのポイント
- 各ステップで局所最適な選択をして全体の解を構築
- 動的プログラミングより単純で高速だが最適解の保証がない場合も
- お釣りの硬貨枚数最小化、活動選択問題が典型例
- 「貪欲選択性質」と「最適部分構造」を持つ問題に適用可能
ひよこ 具体例で教えて？
ペンギン先生 お釣り問題が分かりやすいよ。330円のお釣りを最小枚数で返したい。貪欲法：最大の硬貨から使う→500円玉×0、100円玉×3、50円玉×0、10円玉×3=6枚。日本の硬貨体系ではこれが最適解になる。ただし架空の硬貨体系（1円、3円、4円で6円のお釣り）では貪欲法は4+1+1=3枚だけど、最適は3+3=2枚だよ
ひよこ いつ貪欲法が使えるの？
ペンギン先生 ひよこ DPとの使い分けは？
ペンギン先生 ひよこ IPA試験での出題パターンは？
ペンギン先生 ジョブスケジューリング問題（「締切までに最大数のジョブをこなす」）が典型。締切が早い順に選ぶ貪欲法で最適解が得られる。ハフマン符号化（出現頻度が高い文字に短い符号を割り当てる）も貪欲法の代表例で試験に出やすいよ
まとめ：ざっくりこれだけ覚えればOK！
「貪欲法」って出てきたら「各段階でその時点の最善を選ぶアルゴリズム」と思えればだいたいOK！
📖 おまけ：英語の意味
「Greedy Algorithm」 ＝ 貪欲アルゴリズム
💬 Greedy（欲張りな）。目の前の最善をGreedy（貪欲）に取り続けるアプローチだよ