BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
貪欲法
その時点で最もよい選択をする
貪欲法は、各段階で局所的に最もよいと考えられる選択を行い、通常はその選択を戻さずに解を組み立てる方法です。グリーディ法とも呼びます。手順が単純で効率的になる場合がありますが、どんな問題でも全体の最適解になるわけではありません。問題の性質によって正しさを示せることが重要です。
硬貨の例
金額に対して使える最大の硬貨から選ぶ方法を考えます。硬貨が1、3、4で金額が6なら、最大から選ぶと4+1+1で三枚です。しかし3+3なら二枚で済みます。この例は、局所的に大きい硬貨を選ぶことが、枚数を最小にするとは限らないことを示します。日常の硬貨でうまくいく経験を、任意の条件へ一般化しないようにします。
成功する問題の性質
ある選択を最初に採用しても最適解を失わず、残りが同じ形の問題になることなどを示せれば、貪欲な手順を正当化できます。区間を選ぶ問題や、最小全域木を求める一部の方法などに関係します。ただし、同じ「短いものを選ぶ」でも、何を短さとして比べるかによって結果が変わります。
動的計画法との比較
動的計画法は、部分問題の複数の可能性を結果として保存し、組み合わせて最適なものを求める方法です。貪欲法は選択肢を早く一つに絞るため、記憶量や計算量を抑えられることがあります。その代わり、選んだ後によりよい組合せがなくなるという根拠が必要です。速度だけを見て置き換えることはできません。
試験での確認
問題文で「その時点で最小の費用」「最も早く終了するもの」などの規則が示されたら、その規則どおりに一段ずつ選びます。最適性を問われる場合は、小さな反例を考えると誤った一般化を見つけられます。すべての候補を調べる全探索とも区別します。貪欲法という名称は悪い方法という意味ではなく、適用条件が合えば厳密な最適解を効率よく得られる手法です。条件と結論をセットで理解しましょう。
選択の基準を変えると別のアルゴリズムになります。最小費用、最大利益、最早終了など、問題が何を優先すると定めているかを正確に読み取ります。
参考資料
内容確認日:2026-11-13
用語一覧
5件トランザクション
意味 トランザクションは、複数の処理を一つのまとまりとして扱う単位です。データベースでは、途中まで実行した状態を最終結果として残さず、必要な更新をまと...
トランザクション分離レベル
同時実行時の見え方を決める トランザクション分離レベルは、同時に動く他のトランザクションの変更を、どのように見せるかを定める水準です。一つずつ順番に処...
トリガー
データの変更を契機に動く データベースのトリガーは、行の追加、更新、削除など、あらかじめ定めた出来事に応じて自動的に処理を実行する仕組みです。更新履歴...
動的計画法
部分問題の答えを再利用する 動的計画法は、問題を部分問題へ分け、その結果を保存して再利用することで全体の解を求める方法です。同じ部分問題が繰り返し現れ...
貪欲法
その時点で最もよい選択をする 貪欲法は、各段階で局所的に最もよいと考えられる選択を行い、通常はその選択を戻さずに解を組み立てる方法です。グリーディ法と...