動的計画法が出た院試 過去問
情報の頻出テーマ
定義・定理・計算例から確かめるには:アルゴリズムとデータ構造・動的計画法と貪欲法
動的計画法を出した大学 × 年度
動的計画法の出題例と解説の小見出し
- 北海道大学大学院 情報科学専攻 情報理工学コース 専門科目 2026年度 第4問 — アルゴリズムとデータ構造
ビッグオーの判定 / 最小全域木の確認
- 名古屋大学大学院 複雑系科学 2026年度 第17問 — 情3:整列・二分探索木と最短経路法
バブルソートでは右端から確定する / 平均探索コストは深さの平均で見る
- 東京都立大学大学院 情報科学域 専門科目 2026年度 第4問 — データ構造とアルゴリズム
最後の一手で分類する / a_0=1 の意味
- 名古屋大学大学院 数理情報学 2025年度 第6問 — 離散最適化
増加率の比較 / 再帰木
- 東京大学 数理情報学 2025年度 第5問 — max-plus次数と閉路条件
max-plus への変換 / 収束と正閉路
- 東京科学大学 専門科目(情報工学) 2025年度 第3問 — 格子経路と再帰・動的計画法
最短経路は二項係数 / DP 配列の添字
- 静岡大学大学院 情報科学 2025年度 第2問 — 計算量・再帰・学習
採点観点 / 強化学習の確認
- 京都大学 知能情報学コース 2024年度 第4問 — F2-2 二分探索木と動的計画法
同種を区別しない数え上げ
- 京都大学 数理工学コース 2024年度 第4問 — 専門 第2問:グラフ理論
- 東京大学 創造情報学 専門科目 2024年度 第3問 — 情報システム用語の説明
選択の理由
- 静岡大学大学院 情報科学 2024年度 第2問 — ソフトウェア系
採点観点
- 京都大学 知能情報学コース 2023年度 第4問 — F2-2 アルゴリズムとデータ構造
4葉木はトポロジーを先に固定する
- 大阪大学 専門科目(情報数理学) 2023年度 第1問 — 情報基礎
指数時間と擬多項式時間 / 答案で落としやすい点
- 東京科学大学 専門科目(情報工学) 2023年度 第3問 — スタックと動的計画法
スタックは右端が上 / substring と subsequence の違い
- 名古屋大学大学院 数理情報学 2022年度 第7問 — 第1科目・アルゴリズム設計法
擬多項式時間 / 数えるDP
- 大阪大学 専門科目(情報数理学) 2022年度 第1問 — 情報基礎
中央の配列で分解する / なぜ二分探索で十分か
- 東京大学 創造情報学 専門科目 2022年度 第1問 — 分離資源配分と動的計画法
交換証明の意味 / 採点上の注意
- 静岡大学大学院 情報科学 2022年度 第2問 — ソフトウェア系
採点観点 / 計算量の考察
- 京都大学 知能情報学コース 2021年度 第4問 — F2-2 ナップサック
貪欲法が失敗する理由 / 動的計画法の状態
- 千葉大学大学院 専門科目(A0・A問題・B問題) 2021年度 第6問 — A5 LCS(最長共通部分列)の動的計画法
- 静岡大学大学院 情報科学 2021年度 第2問 — ソフトウェア系
採点観点
- 名古屋大学大学院 数理情報学 2020年度 第8問 — アルゴリズム設計法
Big-Oで分かること / LISの標準解法
- 静岡大学大学院 情報科学 2019年度 第2問 — 情報科学基礎:アルゴリズムとデータ構造
DP表の検算 / 選択肢問題の注意
- 東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2016年度 第2問 — 動的計画法
貪欲法ではない
動的計画法を解答まで読める問題
解説に加えて解答も無料で公開している5問です。院試の対策のほか、学部の授業や期末試験で動的計画法の計算を練習する例題としても使えます。問題文は各大学の公式過去問で確認してください。
- 東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2016年度 第2問 — 動的計画法
貪欲法ではない
- 大阪大学 専門科目(情報数理学) 2022年度 第1問 — 情報基礎
中央の配列で分解する / なぜ二分探索で十分か
- 大阪大学 専門科目(情報数理学) 2023年度 第1問 — 情報基礎
指数時間と擬多項式時間 / 答案で落としやすい点
- 東京大学 創造情報学 専門科目 2024年度 第3問 — 情報システム用語の説明
選択の理由
- 静岡大学大学院 情報科学 2025年度 第2問 — 計算量・再帰・学習
採点観点 / 強化学習の確認
動的計画法が出る試験科目
| 大学・研究科 | 試験科目名 | 出題数 | 出題年度 |
|---|---|---|---|
| 静岡大学大学院総合科学技術研究科 情報学専攻 | 情報科学 | 5 | 2019〜2025(5年度) |
| 京都大学情報学研究科 | 知能情報学コース | 3 | 2021〜2024(3年度) |
| 名古屋大学大学院情報学研究科 | 数理情報学 | 3 | 2020〜2025(3年度) |
| 大阪大学情報科学研究科 情報基礎数学専攻 | 専門科目(情報数理学) | 3 | 2022〜2026(3年度) |
| 東京大学情報理工学系研究科 システム情報学専攻 | 創造情報学 専門科目 | 2 | 2022〜2024(2年度) |
| 東京科学大学情報理工学院 数理・計算科学系 | 専門科目(情報工学) | 2 | 2023〜2025(2年度) |
| 東京大学情報理工学系研究科 システム情報学専攻 | 数理情報学 | 1 | 2025 |
| 千葉大学大学院融合理工学府 先進理化学専攻 物理学コース | 専門科目(A0・A問題・B問題) | 1 | 2021 |
| 北海道大学大学院情報科学院 | 情報科学専攻 情報理工学コース 専門科目 | 1 | 2026 |
| 東京大学学際情報学府 | 学際情報学専攻 先端表現情報学コース 専門科目 | 1 | 2016 |
| 東京都立大学大学院システムデザイン研究科 情報科学域 | 情報科学域 専門科目 | 1 | 2026 |
| 京都大学情報学研究科 | 数理工学コース | 1 | 2024 |
| 名古屋大学大学院情報学研究科 | 複雑系科学 | 1 | 2026 |