Part 4

アルゴリズム ハンズオン

典型アルゴリズムを、Swift で 1 つずつ実装しながら覚えます。

どの章も「まず動くコードを書く → 計算量を確かめる → 演習で使う」の順で進みます。

1. 全探索 候補を漏れなく調べる線形探索と 2 重ループの全列挙。競プロの第一歩。
2. 二分探索 ソート済み配列を半分ずつ絞り込んで O(log N) で探す。めぐる式と答えの二分探索。
3. ソートと貪欲法 sorted(by:) で並べ替え、終了時刻順の貪欲法で区間スケジューリングを解く。
4. 累積和 先頭からの合計を前計算し、区間和クエリに O(1) で答える。定石は prefix[i + 1] = prefix[i] + a[i]。
5. 尺取り法 右を伸ばし左を縮める尺取り法で、条件を満たす最長の連続区間を O(N) で見つける。
6. スタックとキュー LIFO と FIFO の 2 つの取り出し順。removeFirst が O(N) になる罠と括弧の対応判定。
7. DFS と BFS グラフを隣接リストで表し、深さ優先探索と幅優先探索で全頂点をたどる。
8. 動的計画法入門 再帰の爆発をメモ化と DP テーブルで解消し、階段と最小コストの典型に進む。
9. Union-Find グループ分けを管理し、つながっているかをほぼ O(1) で判定するデータ構造。
10. 優先度付きキュー 二分ヒープを自作し、最小値の追加と取り出しを O(log N) で行う。