貪欲法とは？
貪欲法とは、各段階でその時点の最も良い選択肢を選び、一度選んだら後戻りしない設計方針。実装が単純で高速だが、全体としての最適解が保証されるのは問題が特定の条件を満たす場合に限られる。近似解を短時間で得たい場面でも使う。
どんよくほう
貪欲法の意味
各段階でその時点の最も良い選択肢を選び、一度選んだら後戻りしない設計方針。実装が単純で高速だが、全体としての最適解が保証されるのは問題が特定の条件を満たす場合に限られる。近似解を短時間で得たい場面でも使う。
貪欲法の具体例
ハフマン符号の木構築、ダイクストラ法、日本の硬貨での最小枚数の両替が代表例。一方、額面が1・4・5円のような体系では、8円を「5＋1＋1＋1」と選んでしまい最適の「4＋4」を逃す。
貪欲法は試験でどう引っ掛けられる？
「常に最適解が得られる」と覚えると誤る。逆に動的計画法や全探索は最適解を保証するが計算量が大きい、という対比で押さえておく。
貪欲法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。