kobo-ideas / 008
情報系アルゴリズム インタラクティブ可視化
動的計画法・探索・整列・グラフ・データ構造の典型アルゴリズムを、ブラウザで 1 ステップずつ動かして理解する POC 集。
動的計画法（DP）
1 次元 DP
フィボナッチ：再帰木 vs メモ化
素朴な再帰の指数的な木が、メモ化で線形に枝刈りされる。
開く →
1 次元 DPコイン問題（最小枚数）
目標金額を作る最小の硬貨枚数。貪欲が最小にならない例も。
開く →
1 次元 DPLIS：最長増加部分列
各要素で終わる増加列の長さを積み上げ、最長を復元。
開く →
2 次元 DP0-1 ナップサック問題
「入れる / 入れない」で DP テーブルが埋まる。経路復元つき。
開く →
2 次元 DPグリッド経路数
「上＋左」で各マスの通り数が決まる。壁を置いて波及も。
開く →
2 次元 DPLCS：最長共通部分列
2 文字列の一致／不一致で表を埋め、右下から経路復元。
開く →
2 次元 DP編集距離（レーベンシュタイン距離）
挿入・削除・置換の最小回数。実際の編集手順も復元。
開く →
探索・整列・文字列
整列
ソートアルゴリズム可視化
バブル・選択・挿入・マージ・クイックの 5 種を見比べる。
開く →
探索二分探索
整列済みデータで探索範囲を毎回半分に切り捨てる O(log n)。
開く →
文字列照合KMP 文字列照合
部分一致表で、一度照合した文字を見直さずにずらす。
開く →
グラフ
グラフ
グラフ探索：BFS / DFS
迷路を幅優先・深さ優先で探索。広がり方と最短経路の違い。
開く →
グラフダイクストラ法（最短経路）
重み付きグラフで、近い地点から順に最短距離を確定。
開く →
グラフクラスカル法（最小全域木）
辺を安い順に試し、閉路にならなければ採用。
開く →
グラフトポロジカルソート
依存関係（有向グラフ）から実行順を導く。
開く →
データ構造
データ構造
二分探索木（BST）
「小さければ左・大きければ右」で木が組み上がる。
開く →
データ構造二分ヒープ
親が子より大きい木。木と配列の両方で sift を見る。
開く →
データ構造ハッシュテーブル
ハッシュ関数で置き場所を決め、衝突は鎖でつなぐ。
開く →
データ構造Union-Find（素集合データ構造）
グループの併合と「同じグループか」の高速判定。
開く →