アルゴリズムとデータ構造 50 本ノック

学部50 問。全問無料です。

対象読者: 本テーマの各章（計算量と O 記法、データ構造、ソート、探索とハッシュ表、グラフ、動的計画法、P≠NP 予想）を学んだ学部生。小さな入力を手で追って確かめる計算が中心で、特別な数学は仮定しません。

テーマの目次へ（アルゴリズムとデータ構造）

執筆: Claude Code（Sonnet 5.5）・監査 2 回（Claude Code）・最終 2026-10-12

読み込んでいます…

この冊について（出典・構成・使う定理）

主な参考文献

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms
• J. Kleinberg, É. Tardos, Algorithm Design
• M. Sipser, Introduction to the Theory of Computation
• D. E. Knuth, The Art of Computer Programming, Volume 3

問題はすべて Rikai の書き下ろしです。参考文献の演習や本文は転載していません。

構成

• 1〜7: 計算量と O 記法
• 8〜14: 基本的なデータ構造
• 15〜21: ソートアルゴリズム
• 22〜28: 探索アルゴリズムとハッシュ表
• 29〜35: グラフアルゴリズム
• 36〜43: 動的計画法
• 44〜50: P≠NP 予想と NP 完全性

形式: 単一選択 18・複数選択 9・○× 5・数値 7・並べ替え 3・誤り探し 4・記述 4。難易度 ★〜★★★★: 13 / 25 / 11 / 1。

この冊で使う定義・定理（76）

• 定義 3.1 O 記法・Ω 記法・Θ 記法 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 3, 4, 5, 7 番
• 定義 3.2 o 記法・ω 記法 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 4 番
• 命題 3.4 O 記法の計算則 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 5, 7 番
• 命題 5.1 入力を 2 倍にしたときの比 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 2 番
• 命題 3.3 極限による判定法 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 1 番
• 注意 3.7 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 3 番
• 注意 6.2 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 6 番
• 注意 5.2 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 2 番
• 注意 2.6 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 4 番
• 定理 4.2 増大度の階層 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 1, 3 番
• 定理 6.1 マスター定理 計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る → 6 番
• 定義 4.1 単方向連結リスト 基本的なデータ構造：配列・連結リスト・スタック・キュー → 8 番
• 定義 7.1 キュー 基本的なデータ構造：配列・連結リスト・スタック・キュー → 12 番
• 定義 6.1 スタック 基本的なデータ構造：配列・連結リスト・スタック・キュー → 10 番
• 命題 3.2 配列の基本操作の計算量 基本的なデータ構造：配列・連結リスト・スタック・キュー → 9 番
• 命題 4.2 連結リストの基本操作の計算量 基本的なデータ構造：配列・連結リスト・スタック・キュー → 8, 14 番
• 命題 7.2 リングバッファ 基本的なデータ構造：配列・連結リスト・スタック・キュー → 12 番
• 注意 3.5 償却と平均は別のもの 基本的なデータ構造：配列・連結リスト・スタック・キュー → 11, 13, 14 番
• 定理 3.3 動的配列の償却計算量 基本的なデータ構造：配列・連結リスト・スタック・キュー → 9, 11, 13, 14 番
• 系 4.2 フィボナッチ数の線形時間計算 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 36 番
• 系 6.4 ナップサック問題の計算量 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 38, 42 番
• 定義 3.1 部分問題族と依存グラフ 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 37, 41, 43 番
• 定義 7.1 編集距離（レーベンシュタイン距離） 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 40 番
• 定義 6.1 0-1 ナップサック問題 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 39 番
• 定義 5.1 最適部分構造 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 38, 41, 43 番
• 例 5.2 最長単純道では最適部分構造が壊れる 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 38 番
• 命題 6.6 1 次元配列による計算 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 39 番
• 命題 4.1 素朴な再帰の呼び出し回数 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 36 番
• 注意 4.4 単位費用モデルの限界 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 42 番
• 注意 6.3 どの仮定をどこで使ったか 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 42 番
• 定理 7.3 編集距離の漸化式 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 40 番
• 定理 6.2 ナップサック問題の漸化式 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 39 番
• 定理 3.2 動的計画法の計算量 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える → 37, 38, 41, 43 番
• 定義 2.1 グラフ グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 29 番
• 定義 2.2 歩道・道・距離 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 35 番
• 定義 2.3 隣接行列と隣接リスト グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 30, 35 番
• 定義 5.1 重み付き最短経路 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 31, 32 番
• 例 5.6 負の重みがあると正しくない グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 33 番
• 演習 6.1 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 35 番
• 補題 3.1 BFS の不変式 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 30 番
• 補題 4.1 灰色頂点の構造 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 34 番
• 補題 2.5 握手補題 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 29 番
• 補題 5.2 最短路の最適部分構造 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 33 番
• 定理 3.2 BFS の正当性 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 30, 32 番
• 定理 4.2 有向閉路の検出 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 34 番
• 定理 5.3 ダイクストラ法の正当性 グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する → 31, 33 番
• 系 6.2 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 45, 50 番
• 定義 4.1 クラス NP（検証器による定義） P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 44 番
• 定義 6.1 NP 困難と NP 完全 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 45, 46, 49, 50 番
• 定義 5.1 多項式時間多対一帰着（カープ帰着） P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 46, 48, 49 番
• 定義 4.3 充足可能性問題 SAT と 3SAT P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 47 番
• 命題 4.8 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 45 番
• 命題 4.7 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 45 番
• 注意 4.2 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 44 番
• 定理 6.6 独立集合問題の NP 完全性 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 47, 48, 50 番
• 定理 5.2 帰着の基本性質 P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る → 46, 49 番
• 系 4.2 二分探索の最適性 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 28 番
• 系 5.4 負荷率を定数に保てば定数時間 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 25 番
• 定義 5.1 ハッシュ表・ハッシュ関数・負荷率 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 26 番
• 定義 3.1 下限位置 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 23, 24 番
• 定義 6.1 オープンアドレス法 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 27 番
• 例 6.2 線形探査を手で動かし、素朴な削除を壊す 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 27 番
• 定理 3.2 二分探索の正当性 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 23, 24 番
• 定理 3.3 二分探索の比較回数 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 22, 28 番
• 定理 5.3 チェイン法の期待計算量 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 26 番
• 定理 4.1 比較モデルにおける探索の下界 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 28 番
• 定理 6.3 オープンアドレス法の期待探査回数 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 25 番
• 定理 5.7 万能族なら入力の分布を仮定しなくてよい 探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1) → 25 番
• 定義 2.3 転倒（inversion）と転倒数 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 15 番
• 定義 2.4 安定性とin-place性 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 17 番
• 補題 4.1 マージの正当性とコスト ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 17, 18 番
• 補題 5.1 Lomuto 分割の正当性 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 19, 20, 21 番
• 注意 5.4 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 21 番
• 定理 3.1 バブルソートの正当性と操作回数 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 15, 16, 17 番
• 定理 4.2 マージソートの正当性と計算量 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 18, 19 番
• 定理 5.2 決定的クイックソートの最悪計算量 ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」 → 19, 20, 21 番