「computer-science」タグのついた8記事

グラフの語彙と 2 つの表し方から、幅優先探索と深さ優先探索の使い分けを解説します。BFS が重みなし最短経路になる理由、訪問済み集合が要る理由、トポロジカルソートによる依存関係の順序づけと循環検出、状態を頂点と見なす発想を扱います。

配列・連結リスト・スタック・キュー・ハッシュマップ・木・トライ木の得手不得手を、操作ごとの計算量で比較します。スタックが LIFO でキューが FIFO であること、ハッシュマップの平均 O(1) が成り立つ理由と最悪の場合、トライ木が前方一致に強い理由を扱います。

ビット演算子 (AND・OR・XOR・NOT・シフト) の働きと、複数の真偽値を 1 つの整数にまとめるビットフラグの実装を解説します。フラグの判定・追加・削除・反転の書き方、マスクの作り方、JavaScript のビット演算が 32 ビット符号付きで動く点を扱います。

二分探索の仕組みを、探索範囲を毎回半分にするという不変条件から解説します。実装の落とし穴 (中央値の求め方・境界条件・無限ループ)、時間計算量と空間計算量、反復と再帰で空間が変わる理由、適用条件を扱います。

再帰を基底ケースと再帰ステップの 2 つに分けて設計する方法を解説します。再帰木で手数を数えること、コールスタックが空間を食うこと、分割統治としてのマージソートとクイックソート、安定ソートが要る場面、再帰と反復の使い分けを扱います。

部分問題の重なりに気づくところから動的計画法を導きます。メモ化と表埋めの対応、適用できる 2 つの条件、状態数と遷移コストによる計算量の見積もり、直前の行だけ持つ空間圧縮、貪欲法との違いを扱います。

O 記法の読み方を、定数倍と低次項を捨てるという考え方から解説します。代表的なオーダーの体感、時間計算量と空間計算量の区別、ループや再帰からオーダーを数える手順、最悪と平均の使い分けを扱います。

二重ループを一重に落とす 4 つの型を、適用条件から整理します。two pointer、固定長と可変長のスライディングウィンドウ、累積和による区間和、単調スタックによる「次に大きい要素」を扱い、どの型が当たるかの判定手順を示します。