尺取り法について
2024年1月31日概要 尺取り法についてまとめる。 英語だと、Two Pointer ApproachまたはTwo Pointer Techniqueと呼ばれる。 尺取り法とは データセット（数列や文字列など）の右端と左端のインデックスを保持して、条件によって左右のインデックスを移動させることで、条件を満たすデータを探索するアルゴリズム。 特定の条件を満たすデータを区間の中から探索したいような時に役立つ。 例題 配...
概要 尺取り法についてまとめる。 英語だと、Two Pointer ApproachまたはTwo Pointer Techniqueと呼ばれる。 尺取り法とは データセット（数列や文字列など）の右端と左端のインデックスを保持して、条件によって左右のインデックスを移動させることで、条件を満たすデータを探索するアルゴリズム。 特定の条件を満たすデータを区間の中から探索したいような時に役立つ。 例題 配...
概要 グラフを表現するためのデータ構造である隣接リストと隣接リストについてまとめる。 隣接リストや隣接行列は有向グラフでも無向グラフでも利用できる。 隣接リスト（Adjacency List） 各頂点（ノード）ごとに隣接する頂点をリストとして持つデータ構造。 // 無向グラフの例 A---B | / | | / | C---D // 隣接リストで表現すると、次のような形になる A: [B...
概要 二分探索木とは どのノードにおいても、左の子ノード＜親ノード＜右の子ノードとなるような木。 ex. 5 / \ 3 8 / \ / \ 1 4 6 9 探索パターン 深さ優先探索（DFS: Depth first search） それぞれのノード探索順はwww.momoyama-usagi.com - うさぎでもわかる2分探索木 後編 2分探索木における4つの...
Goでスタックとキューをそれぞれ実装してみた。 スライスを使ったパターンと連結リストを使ったパターンをそれぞれ実装している。 個人的にはスライスを使ったパターンの方が実装は楽かなと思う。 スタックのpush、pop、キューのenqueue、dequeueの時間計算量はそれぞれO(1)で実装できるが、一部サボってO(N)になってしまっているものがある。 スタック ソースコード：stack 連結リスト...
連結リストの走査で役立つランナーテクニックについてまとめる。 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法で紹介されていて初めて知った。 ランナーテクニックとは 連結リストの先頭から走査していくポインタと、そのポインタより先から走査していくポインタの2種類を用意して、同時に走査していく方法。 これが何に役立つかというと、例えば次のような例題を解くのに役立つ。 例題 単...
概要 コーディングクイズを解く日課を再開するに当たって、リハビリを兼ねてアルゴリズムとデータ構造の基本について復習。 配列 連続した配置でメモリを確保する 単一のデータ型 サイズは一般的には固定だが、言語によっては動的（可変長配列） サブアレイ 配列内から連続した形で取り出される配列 [1, 2, 3, 4, 5] →[2, 3, 4] サブシーケンス 要素順を変更せずに、一部の要素...
カウントソートとは ソートアルゴリズムの中でも比較を使わずにソートする変わった？アルゴリズム。 比較せずに要素をカウントすることでソートができる。 カウントしてソートすることができるというのは不思議！と思ったので調べてみた。 前提 累積和について知っておく必要がある。 cf. qiita.com - 累積和とは（超初心者用） 実装 ソースコードは以下。 count_sort package mai...
バックトラッキングとは 指定された制約を満たすような組み合わせを探索するアルゴリズム。 重複しない組み合わせ（nCr）を全て探索するようなときに使える。 実装 ソースコードは以下。 backtrack 与えられた配列からN個の重複しないサブシーケンスを取得する処理。 以下は4C3の例。 package main import "fmt" func backtrack(rs...
スライディングウィンドウとは 配列のサブアレイを”ウィンドウ（サブセット）”をずらすしていくように探索するアルゴリズム。 ウィンドウサイズは固定または動的。 実例としては、レートリミッターで使われたりする。 実装 ソースコードは以下。 sliding_window 与えられた配列から合計がN以上になるサブアレイを探索する関数。 package main import "fmt"...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 クイックソート データ列の中から適当なデータ（ピボット）を選択し、ピボットより小さいデータを前方、大きいデータを後方に移動させる。 分割されたデータをそれぞれソートする 分割統治法の一種 計算時間 最悪計算時間 O(n²) ...