アルゴリズムとデータ構造の全体像
アルゴリズムとデータ構造は、コンピュータサイエンスの土台となる分野です。このページでは、計算量の考え方から始まり、配列・リストといった身近な構造、探索やソート、動的計画法、グラフ・文字列処理まで、整理しています。一通り学んでいくと、「この処理はどれくらい速いのか」「どのデータ構造で持つと自然か」といった判断が自分でできるようになるはずです。競技プログラミングやコーディング面接はもちろん、実務で設計判断を求められる場面でも手の内が広がる構成になっています。
1. 基礎概念と計算量
プログラムの効率を測るための共通言語を学ぶ分野です。以降で扱うどのアルゴリズムも「どれくらい速いか」「どれくらいメモリを使うか」という観点で比較されるので、ここでの考え方が全体を貫く物差しになります。
1.1 アルゴリズムとは
アルゴリズムの定義や、良いアルゴリズムが満たすべき性質を確認する入口です。まずは次の4本を読むと、このあとの計算量や探索・ソートの節が読みやすくなります。
1.2 計算量
実行時間やメモリ使用量を、入力サイズの関数として捉える考え方を学びます。オーダー記法を使うことで、異なるアルゴリズムを同じ尺度で比較できるようになります。
- 時間計算量と空間計算量
- オーダー記法(O, Ω, Θ)
- 最悪・平均・最良計算量
- 典型的な計算量クラス(O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ))
- ならし計算量(amortized analysis)の考え方
1.3 再帰と分割統治
問題を小さな問題に分解して解く基本パターンを押さえます。後に出てくる探索・ソート・動的計画法のいずれにもつながる、思考の基礎道具です。
- 再帰関数の書き方と終了条件
- 再帰木と計算量の見積もり
- 分割統治の枠組み
- マスター定理の初歩
2. 基本的なデータ構造
データをどう並べて保持するかで、できる操作とその速さが変わります。ここでは配列・リスト・ハッシュといった線形的な構造を中心に、操作とコストの対応関係を整理します。
2.1 配列と動的配列
連続したメモリに要素を並べる、基本的な構造です。添字アクセスの速さと、末尾以外の挿入・削除の重さという特徴を、具体例を通して理解します。
- 静的配列の構造とアクセス
- 動的配列(可変長配列)
- 容量と要素数
- 拡張時のコストとならし計算量
- 多次元配列
2.2 連結リスト
要素を「次の要素へのリンク」でつないでいくデータ構造です。配列と比べたときの得意・不得意を整理し、どちらを選ぶべきか判断できるようになります。
- 単方向リストと双方向リスト
- 挿入・削除・探索の計算量
- 循環リスト
- 配列との使い分け
2.3 スタックとキュー
「最後に入れたものから取り出す」「最初に入れたものから取り出す」という基本的なデータ構造です。後のDFS・BFSなど、多くのアルゴリズムで道具として繰り返し登場します。
- スタック(LIFO)の操作と実装
- キュー(FIFO)の操作と実装
- デック(両端キュー)
- 配列実装とリスト実装
2.4 ハッシュテーブル
キーから値を平均O(1)で引けるようにする仕組みです。内部の工夫を知っておくと、言語組み込みの辞書型や集合型への理解もぐっと深まります。
- ハッシュ関数の性質
- 衝突処理
- チェイン法
- オープンアドレス法
- 負荷率とリハッシュ
- 集合(set)と連想配列(map)としての使い方
3. 木構造と優先度付きキュー
階層的なデータや、「最小値や最大値を素早く取り出したい」場面で活躍する構造を扱います。単純な二分木からバランス木・ヒープまで、段階的に見ていきます。
3.1 木の基礎
木構造の用語と基本的な走査方法を押さえる入口です。後の二分探索木・ヒープ、さらには構文木などあらゆる応用の土台になります。
- 木の用語(根・葉・深さ・高さ)
- 二分木の表現
- 木の走査
- 前順・中順・後順
- 幅優先探索
3.2 二分探索木
左右の大小関係を保つことで、探索・挿入・削除を効率化する木です。平均的な計算量と、偏ったときの最悪計算量の違いに注目します。
- 二分探索木の定義と性質
- 探索・挿入・削除
- バランスが崩れる例
3.3 ヒープと優先度付きキュー
最大値や最小値を効率よく取り出したい要求に応える構造です。ダイクストラ法やハフマン符号など、後の応用アルゴリズムでも繰り返し使われます。
- 二分ヒープの構造
- 挿入と取り出しの操作
- ヒープ構築(O(n))
- ヒープソート
- 優先度付きキューの使いどころ
3.4 Union-Find(素集合データ構造)
「同じグループに属するか」を素早く判定する構造です。グラフの連結成分や、最小全域木アルゴリズムの基本道具として使われます。
- 要素の管理と代表元
- Union操作とFind操作
- 経路圧縮とランクによる最適化
4. 探索とソート
目的の要素を取り出す「探索」と、データを並べ替える「ソート」は、もっとも基本的なタスクです。どちらも派生が豊富で、計算量の違いを味わえる題材でもあります。
4.1 線形探索と二分探索
配列から目的の要素を探す、代表的な2つの方法を比較します。ソート済みであることがなぜ強力な武器になるのか、ここで体感できます。
- 線形探索
- 二分探索
- 整数上の二分探索
- 実数上の二分探索
- 境界を求める二分探索(lower_bound / upper_bound)
4.2 基本的なソート
まずは素朴なソートアルゴリズムを通して、比較と交換の考え方を押さえます。効率は良くありませんが、アルゴリズム設計のウォームアップとして重要です。
- バブルソート
- 選択ソート
- 挿入ソート
- 安定ソートとは何か
4.3 高速なソート
分割統治などの工夫でO(n log n)を達成するソートを学びます。標準ライブラリのソートが内部でどう動いているかをイメージできるようになります。
- マージソート
- クイックソート
- ピボット選択
- 平均と最悪の計算量
- ヒープソート
- 比較ソートの下界(Ω(n log n))
4.4 線形時間ソート
比較に頼らず、データの性質を利用して並べ替える手法です。使える場面は限られますが、条件が合えばとても強力です。
- 計数ソート
- バケットソート
- 基数ソート
5. アルゴリズム設計技法
問題を解くための「考え方のパターン」を身につける分野です。新しい問題に出会ったときに、どの枠組みで攻めればよいか当たりをつけられるようになります。
5.1 全探索
候補をすべて調べて確実に答えを出す、もっとも基本的な戦略です。計算量は重くなりがちですが、「まず全探索で解けるか考える」姿勢は後のすべてに生きてきます。
- 総当たりによる全探索
- bit全探索
- 順列全探索
- バックトラッキング(枝刈り)
5.2 貪欲法
その場での最善を選び続けることで、全体の最適解にたどり着く手法です。いつ使えて・いつ使えないのかの見極めを中心に学びます。
- 貪欲法の基本アイデア
- 典型問題(区間スケジューリングなど)
- 交換論法による正当性の証明
- 貪欲が通らない例と動的計画法への橋渡し
5.3 動的計画法(DP)
部分問題の答えを表にためて再利用することで、計算量を落とす強力な手法です。典型パターンを押さえると、応用問題でも枠組みが見えてきます。
- メモ化再帰と漸化式
- ナップサック問題(0-1 / 個数制限なし)
- 最長共通部分列(LCS)・編集距離
- 区間DP・bit DPの入口
- 状態の設計と計算量
5.4 二分探索を使った設計
「答えを決め打ちして判定問題に落とす」など、単なる要素探索を超えた二分探索の活用法です。発想として使えると、一気に解ける問題の幅が広がります。
- 答えで二分探索(めぐる式二分探索)
- 条件を満たす境界を求める
- 判定問題への置き換え
6. グラフアルゴリズム
ノードとエッジで表現される「つながり」を扱う分野です。経路探索・ネットワーク設計・依存関係の管理など、実世界の問題と直結しています。
6.1 グラフの表現と基本
グラフを計算機でどう保持するか、どこから手をつけるかを押さえます。後のどのグラフアルゴリズムにも共通する土台となる部分です。
- 有向グラフと無向グラフ
- 重み付きグラフ
- 隣接行列と隣接リスト
- 次数・連結・閉路などの用語
6.2 グラフ探索
グラフ上を歩いて情報を集める、もっとも基本の操作です。到達可能性・重みなしの最短経路・連結成分など、多くの問題がこの2つで解けます。
- 深さ優先探索(DFS)
- 再帰とスタックによる実装
- 行きがけ順・帰りがけ順
- 幅優先探索(BFS)
- 重みなしの最短経路
- 連結成分の列挙
6.3 最短経路
重み付きグラフで、2点間の最短距離を求めるアルゴリズムを扱います。負の辺の有無など制約に応じた使い分けができるようになります。
- ダイクストラ法(優先度付きキュー版)
- ベルマン・フォード法
- ワーシャル・フロイド法
- 各手法の計算量と適用条件
6.4 最小全域木
すべての頂点をつなぐ最小コストの木を求める問題です。貪欲法とUnion-Findの応用として位置づけられ、ネットワーク設計の基本モデルにもなります。
- クラスカル法
- プリム法
6.5 トポロジカルソートとDAG
依存関係のあるタスクを順序付ける手法です。ビルドシステムやスケジューリングなど、身近な応用を持ちます。
- 有向非巡回グラフ(DAG)
- トポロジカルソート
- DAG上のDP
7. 文字列アルゴリズム
文字列を効率よく扱うための手法を学びます。テキスト検索や自然言語処理の前処理など、応用範囲の広い分野です。
7.1 文字列の基本処理
文字列を配列として扱うときの基本操作を押さえます。言語組み込みの便利な関数の裏側で何が起きているか、イメージできるようになります。
- 文字と文字コード(ASCII、UTF-8の概要)
- 部分文字列・連結・比較の計算量
- 文字列と配列の対応
7.2 文字列検索
長いテキストの中からパターンを探す、代表的な問題です。素朴な方法から、前処理を使って高速化する手法まで段階的に見ていきます。
- 素朴な文字列照合
- KMP法の考え方
- ローリングハッシュによる照合
- 応用(重複検出・回文探索の入口)