データ構造・アルゴリズム・プログラミング 入門学習
計算量・データ構造・探索と整列・グラフのアルゴリズムと、擬似言語プログラムのトレース方法を学ぶ
第1章 計算量と応用数学の基礎
アルゴリズムの効率は、データ件数nが増えたときに処理時間がどう増えるかを表す計算量（オーダ記法）で比較します。定数倍や小さい項は無視し、最も増え方の大きい項だけで表すのが基本です。例えば、処理回数が 3n²＋5n＋2 なら O(n²) です。
| オーダ | 増え方のイメージ | 代表例 |
|---|---|---|
| O(1) | nに関係なく一定 | 配列の添字アクセス、ハッシュ表の探索（平均） |
| O(log n) | nが2倍になっても1回分増えるだけ | 2分探索 |
| O(n) | nに比例 | 線形探索 |
| O(n log n) | nに比例よりやや大きい | マージソート、クイックソート（平均）、ヒープソート |
| O(n²) | nが2倍で4倍 | バブルソート、選択ソート、挿入ソート |
応用数学では、データ分析やAIの土台となる線形代数（行列・逆行列・転置行列・単位行列、固有値・固有ベクトル）が出題範囲です。主成分分析は共分散行列の固有値・固有ベクトルを求める手法と結びついています。方程式を数値的に解く近似解法として、解を含む区間を半分ずつ狭める二分法、接線を使って解に近づけるニュートン法、面積を近似する数値積分（シンプソン法など）、微分方程式を少しずつ進めて解くオイラー法があります。
情報理論の分野では、符号理論、一般的な前提から個別の結論を導く演繹推論と個別の事例から一般則を導く帰納推論、オートマトン（状態と入力による状態遷移で文字列を受理するモデル）なども押さえておきましょう。
- オーダ記法は最大次数の項だけを残し、係数を無視する
- 2分探索はO(log n)、線形探索はO(n)
- 比較による整列は、単純な方式がO(n²)、効率的な方式がO(n log n)
- 二分法は区間を半分ずつ狭める、ニュートン法は接線で近づける（収束が速い）
- 主成分分析は共分散行列の固有値・固有ベクトルと関係する
第2章 データ構造の種類と使い分け
配列は同じ型のデータを連続して並べ、添字で任意の要素にすぐアクセスできます。要素数が固定の静的配列と、実行中に伸縮できる動的配列があり、表形式のデータには多次元配列を使います。連結リストは各要素が次の要素へのポインタを持つ構造で、途中への挿入・削除はポインタの付け替えだけで済みますが、k番目の要素にたどり着くには先頭から順にたどる必要があります。末尾が先頭につながったものを環状リストといいます。
| データ構造 | 特徴 | 利用場面の例 |
|---|---|---|
| スタック | 後入れ先出し（LIFO）。push で積み、pop で最後に積んだものを取り出す | 関数呼出しの管理、括弧の対応チェック、深さ優先探索 |
| キュー | 先入れ先出し（FIFO）。enqueue で末尾に追加、dequeue で先頭から取り出す | 処理待ち行列、幅優先探索、ストリームのバッファ |
| 2分探索木 | 左の子孫＜節＜右の子孫となるよう配置 | 順序を保った高速な探索（偏ると性能が低下） |
| ヒープ | 親が子以上（または以下）となる完全2分木 | 優先度付きキュー、ヒープソート |
| ハッシュ表 | キーからハッシュ関数で格納位置を計算 | 辞書・重複チェック（衝突への対処が必要） |
| グラフ | 頂点と辺で関係を表す（有向・無向、重み付き） | 経路探索、ネットワーク、ナレッジグラフ |
木構造には、子の並び順に意味がある順序木、子を3つ以上持てる多分木、探索のための探索木などがあります。2分探索木を中間順（左→節→右）でなぞると、値の小さい順に取り出せます。ハッシュ表では、異なるキーが同じ位置になる衝突（シノニム）への対処として、同じ位置の要素をリストでつなぐ方法などがあります。科目B（4-2）では、データ構造を操作するプログラムを読み、データがどう変化するかを正しく把握するスキルが問われます。
- スタック＝LIFO（最後に入れたものが最初に出る）、キュー＝FIFO
- 配列はランダムアクセスが速い、連結リストは挿入・削除が速い
- 2分探索木は中間順でたどると昇順に並ぶ
- ハッシュ表の探索は平均O(1)だが、衝突への対処が必要
- 深さ優先探索はスタック、幅優先探索はキューと相性がよい
第3章 探索・整列・文字列処理のアルゴリズム
線形探索法は先頭から順に比較する方法で、整列されていないデータにも使えます。2分探索法は整列済みのデータに対して中央の要素と比較し、探索範囲を半分ずつに狭める方法で、比較回数はおよそ log₂n 回です。
| 整列法 | 考え方 | 計算量（平均） |
|---|---|---|
| バブルソート | 隣り合う要素を比較し、逆順なら交換することを繰り返す | O(n²) |
| 選択ソート | 未整列部分から最小値を選び、先頭と交換する | O(n²) |
| 挿入ソート | 整列済み部分の適切な位置に要素を挿入する。ほぼ整列済みのデータに強い | O(n²) |
| クイックソート | 基準値（ピボット）より小さい群と大きい群に分け、再帰的に整列（分割統治） | O(n log n)（最悪O(n²)） |
| マージソート | 半分に分けて整列し、整列済みの列を併合する（分割統治） | O(n log n) |
| ヒープソート | ヒープを構成し、最大（最小）値を順に取り出す | O(n log n) |
自分自身を呼び出す再帰は、問題を同じ形の小さな問題に分ける分割統治と相性がよい手法です。再帰では必ず終了条件を設け、それがないと呼出しが止まりません。
文字列照合では、パターンを1文字ずつずらす単純な方法に対し、照合に失敗したとき既に一致した部分の情報を使ってずらし幅を大きくするKMP法や、パターンの末尾から比較してずらし幅を決めるBM法があります。自然言語処理では、文を単語に分割して品詞を付与する形態素解析、文法構造を調べる構文解析、文節同士の修飾関係を調べる係り受け解析、連続するn個の文字・単語を単位とするn-gram、文章をベクトルにして比較する文章間類似度などを押さえましょう。ほかに、最適解ではなく許容できる精度の解を短時間で求める近似アルゴリズム、乱数を利用する確率アルゴリズム、データ圧縮のアルゴリズムも範囲に含まれます。
- 2分探索は整列済みデータが前提。比較回数は約log₂n回
- クイックソート・マージソートは分割統治。クイックソートは最悪O(n²)
- 挿入ソートはほぼ整列済みのデータで高速
- 再帰には必ず終了条件（基底条件）を置く
- KMP法・BM法は照合失敗時のずらし幅を工夫して文字列探索を高速化
第4章 グラフのアルゴリズム
グラフの最短経路問題には、目的に応じて複数のアルゴリズムがあります。ダイクストラ法は1つの出発点から各頂点への最短経路を求める方法で、確定した頂点から未確定の頂点への距離を更新し、最も近い頂点を順に確定させていきます。ただし、辺の重みに負の値があると正しく求められません。ベルマン・フォード法は負の重みの辺があっても使え、負の閉路（一周すると距離が減り続ける閉路）の検出もできます。ワーシャル・フロイド法は、すべての頂点の組の最短経路をまとめて求めます。
| アルゴリズム | 求めるもの | 特徴 |
|---|---|---|
| ダイクストラ法 | 1点から全頂点への最短経路 | 負の重みの辺は扱えない |
| ベルマン・フォード法 | 1点から全頂点への最短経路 | 負の重みに対応、負の閉路を検出できる |
| ワーシャル・フロイド法 | 全頂点の組の最短経路 | 中継点を1つずつ増やしながら距離表を更新 |
| クラスカル法 | 最小全域木 | 重みの小さい辺から、閉路を作らないものを順に採用 |
| プリム法 | 最小全域木 | 1頂点から始め、つながっている頂点集合から最も軽い辺で木を広げる |
最小全域木（MST）は、すべての頂点を閉路なしで結ぶ辺の集合のうち、重みの合計が最小のものです。拠点間の配線や配送網の設計で使われます。最大フロー問題は、各辺に容量があるネットワークで、出発点から終点へ流せる量の最大値を求める問題です。
これらは配車ルートの最適化や物流ネットワークの分析など、データ活用の場面でも登場します。手順を図や表で追えるよう、小さなグラフで実際に距離表を更新してみることが理解の近道です。
- ダイクストラ法は負の重みの辺があると使えない
- 負の重み・負の閉路にはベルマン・フォード法
- 全頂点の組の最短経路はワーシャル・フロイド法
- 最小全域木：クラスカル法（辺を軽い順）、プリム法（頂点から木を広げる）
- 最大フロー問題は辺の容量の制約の下で流せる最大量を求める
第5章 擬似言語プログラムの読み方とトレース
科目B（4-2、4-3）では、データ構造やアルゴリズムを実装したプログラムを読み解き、動作を正しく把握するスキルが問われ、IPA公開のサンプル問題でも擬似言語のプログラムが出題されています。擬似言語では、○で始まる行が関数の宣言、←が代入、if ～ elseif ～ else ～ endifが選択、while ～ endwhileやfor ～ endforが繰返しです。配列の要素番号は、問題文で特に断りがなければ1から始まる点に注意しましょう。
次は、昇順に整列済みの配列 a から key を2分探索し、見つかった要素番号を返すプログラムです。
○整数型: binSearch(整数型の配列: a, 整数型: key)
整数型: lo ← 1
整数型: hi ← aの要素数
整数型: mid
while (lo ≦ hi)
mid ← (lo ＋ hi) ÷ 2 の商
if (a[mid] ＝ key)
return mid
elseif (a[mid] < key)
lo ← mid ＋ 1 // 右半分に絞る
else
hi ← mid － 1 // 左半分に絞る
endif
endwhile
return －1 // 見つからなかった
a ＝ {3, 8, 12, 17, 25, 31, 40}、key ＝ 25 としてトレース（変数の値を1行ずつ追うこと）してみます。
| 回 | lo | hi | mid | a[mid] | 判定と処理 |
|---|---|---|---|---|---|
| 1 | 1 | 7 | 4 | 17 | 17 < 25 なので lo ← 5 |
| 2 | 5 | 7 | 6 | 31 | 31 > 25 なので hi ← 5 |
| 3 | 5 | 5 | 5 | 25 | 一致したので 5 を返す |
トレースのコツは、①変数ごとに列を作った表を用意する、②ループの1周ごとに1行を埋める、③「商」「切捨て」「四捨五入」などの指定を正確に計算する、④ループの終了条件（ここでは lo ≦ hi）を毎回確認する、の4点です。また、境界値（要素数1、見つからない場合、先頭・末尾の要素）で試すと、誤りのある箇所を見つけやすくなります。
データ記述言語として、カンマ区切りのCSV、キーと値・配列で階層を表すJSON、タグで構造を表すXML、インデントで階層を表し設定ファイルやデータコントラクトの記述にも使われるYAMLの読み方も押さえておきましょう。データ分析・AIの分野ではPythonやRがよく使われます。
- ←は代入、○は関数宣言。配列の要素番号は原則1から
- トレースは変数ごとの表を作り、ループ1周ごとに値を記録する
- 「÷ 2 の商」のような整数演算の指定を見落とさない
- 境界値（要素数1・該当なし・先頭/末尾）で動作を確認する
- YAMLはインデントで階層を表す（データコントラクトの記述でも登場）