BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
動的計画法
部分問題の答えを再利用する
動的計画法は、問題を部分問題へ分け、その結果を保存して再利用することで全体の解を求める方法です。同じ部分問題が繰り返し現れる場合に、毎回計算し直す無駄を減らせます。DPと略されます。最適化問題だけでなく、個数を数える問題や到達可能性の判定などにも利用されます。
状態と遷移
何を保存するかという状態の定義と、既に求めた状態から次の状態をどう求めるかという遷移を決めます。例えば階段を一段か二段ずつ上る方法の数なら、ある段への到達方法は一つ前と二つ前の段から来る方法に分けられます。保存する情報が不足すると正しい結果を求められず、多すぎると記憶量が膨らみます。
Pythonによる例
def count_stair_ways(steps):
if steps < 0:
return 0
ways = [0] * (steps + 1)
ways[0] = 1
for current in range(1, steps + 1):
ways[current] = ways[current - 1]
if current >= 2:
ways[current] += ways[current - 2]
return ways[steps]
0段へは何もしない一通りがあると定義し、小さい段から順に求めています。
メモ化との関係
再帰呼出しの結果を保存する上からの方法と、必要な順序で表を埋める下からの方法があります。どちらも同じ部分問題の再計算を避ける考え方を使えます。ただし、依存関係に循環がある場合や、状態の数が非常に大きい場合は、そのまま簡単に適用できるとは限りません。
貪欲法との違い
貪欲法はその時点でよさそうな選択を確定して進みます。動的計画法は複数の部分的な候補の結果を比較し、全体につなげます。試験では、配列の各要素が何を意味するか、初期値、更新順序を確認します。同じ配列を上書きする場合は、更新済みの値を使ってよいかが重要です。計算量は状態数と一状態あたりの遷移数から考えましょう。
参考資料
内容確認日:2026-11-13
用語一覧
5件トランザクション
意味 トランザクションは、複数の処理を一つのまとまりとして扱う単位です。データベースでは、途中まで実行した状態を最終結果として残さず、必要な更新をまと...
トランザクション分離レベル
同時実行時の見え方を決める トランザクション分離レベルは、同時に動く他のトランザクションの変更を、どのように見せるかを定める水準です。一つずつ順番に処...
トリガー
データの変更を契機に動く データベースのトリガーは、行の追加、更新、削除など、あらかじめ定めた出来事に応じて自動的に処理を実行する仕組みです。更新履歴...
動的計画法
部分問題の答えを再利用する 動的計画法は、問題を部分問題へ分け、その結果を保存して再利用することで全体の解を求める方法です。同じ部分問題が繰り返し現れ...
貪欲法
その時点で最もよい選択をする 貪欲法は、各段階で局所的に最もよいと考えられる選択を行い、通常はその選択を戻さずに解を組み立てる方法です。グリーディ法と...