アルゴリズム・データ構造の無料テキスト：Jeff Erickson のオープンテキスト

概要¶

Illinois 大学 Jeff Erickson 教授による無料アルゴリズム教科書（jeffe.cs.illinois.edu）の紹介。FAANG・テック企業の面接でよく出るアルゴリズムが網羅されており、無料で PDF ダウンロードが可能。

詳細¶

Jeff Erickson の Algorithms テキストとは¶

URL: http://jeffe.cs.illinois.edu/teaching/algorithms/
Illinois 大学 CS の学部・大学院向け教科書
完全無料・CC ライセンス（PDF ダウンロード可）
800ページ以上で証明・擬似コード付き

カバーされている主なトピック¶

再帰とバックトラッキング¶

# N クイーン問題（バックトラッキング）
def solve_nqueens(n):
    def is_valid(board, row, col):
        for i in range(row):
            if board[i] == col: return False
            if abs(board[i] - col) == abs(i - row): return False
        return True

    def backtrack(board, row):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                backtrack(board, row + 1)

    result = []
    backtrack([-1] * n, 0)
    return result

動的計画法（DP）¶

よく出る DP パターン:

1. 1次元DP: フィボナッチ、コイン問題
2. 2次元DP: 最長共通部分列（LCS）、編集距離
3. 区間DP: 行列チェーン積、バルーンバースト
4. メモ化再帰: 上記の top-down 版

メモ化再帰の例（コイン問題）:
  dp[i] = amount i を作るのに必要な最小枚数
  dp[0] = 0
  dp[i] = min(dp[i - coin] + 1) for coin in coins if i >= coin

グラフアルゴリズム¶

BFS: 最短経路（重みなし）、幅優先探索
DFS: 連結成分、トポロジカルソート、サイクル検出
Dijkstra: 最短経路（重みあり・非負）O(E log V)
Bellman-Ford: 最短経路（負の重みあり）O(VE)
Floyd-Warshall: 全点対最短経路 O(V³)
Union-Find: 連結成分の高速判定
MST(Prim/Kruskal): 最小全域木

ソート・探索¶

計算量の比較:
  O(n²): バブルソート、挿入ソート（小データには有効）
  O(n log n): マージソート（安定）、クイックソート（平均）、ヒープソート
  O(n): カウンティングソート、基数ソート（整数限定）

二分探索の変種:
  - 左端・右端の検索（lower_bound, upper_bound）
  - 回転配列での二分探索
  - 答えで二分探索（最小値の最大化など）

面接対策としての使い方¶

優先度の高いチャプター:

1. Recursion（再帰）
   → バックトラッキングの土台
2. Dynamic Programming
   → 面接最頻出カテゴリ
3. Graphs（グラフ）
   → BFS/DFS/Dijkstra は必須
4. Divide and Conquer
   → マージソート、クイックソートの理解

学習順序:
  配列/文字列 → 再帰 → DP → グラフ → 木 → 高度なデータ構造

なぜ重要か / いつ使うか¶

FAANG面接前の網羅的な学習: LeetCode と組み合わせて理論背景を補強
無料で高品質: CS専門書として有料書籍に匹敵する内容が無料
証明付き: なぜそのアルゴリズムが正しいのかを理解するため（面接でも「なぜ?」を聞かれる）
競技プログラミング: アルゴリズムの標準的な実装・計算量理解に必須