アルゴリズムの基礎知識まとめ(随時更新)

ソート

• バブルソート
  • 隣り合う数字の大小を比較して整列するアルゴリズム
  • 計算量
    • O(n^2)
  • 使用例
    • データ量が少ない場合
• クイックソート
  • 分割統治法を利用したアルゴリズム
    • 基準値を決めて大きい値と小さい値のグループに分ける
    • そのグループの中でさらに基準値を決めてグループに分ける
    • これを繰り返して整列させる
  • 計算量
    • O(n log n)
  • 使用例
    • 高速にソートしたい場合
• マージソート
  • 要素数が1になるまで2分割を繰り返し、分割した要素同士を並び替えながら併合していくアルゴリズム
  • 計算量
    • O(n log n)
  • 使用例
    • 安定的にソートしたい場合

探索

• 全探索
  • 虱潰しに全ての組み合わせを探索する方法
  • 種類と使用例
    • 全探索
      • データ量が少ない場合
    • bit全探索
      • 部分集合を全パターン列挙する場合
    • 幅優先探索(BFS)
      • キューを使って始点から近い順に探索していく場合
    • 深さ優先探索(DFS)
      • スタックを使って幅より深さを優先して探索する場合
• 線形探索
  • 先頭から順番に値を探索する方法
  • 使用例
    • データ量が少ない場合
• 二分探索
  • 2分割して条件に合わない方を消していき、目的の値が見つかるまで繰り返して探索する方法
  • 使用例
    • データ量が多い場合

データ構造

• 連結リスト
  • 各要素が前や次の要素のリンクを持つデータ構造
  • 種類と例
    • 単方向連結リスト
      • 列車
    • 双方向連結リスト
      • 総武線
    • 循環連結リスト
      • 山手線
• スタック
  • 要素が入ってきた順に値を入れ、後に入れた要素から取り出すデータ構造
  • LIFO(後入れ先出し)もしくはFILO(先入れ後出し)
  • 例
    • 積み木
• キュー
  • 要素が入ってきた順に値を入れ、先に入れた要素から取り出すデータ構造
  • FIFO(先入れ先出し)もしくはLILO(後入れ後出し)
  • 例
    • 待ち行列
• 木
  • 一つの要素が複数の子要素を持ち、階層が深くなるにつれて枝分かれするデータ構造
  • 種類と例
    • 二分木
      • 細胞分裂
    • 多分木
      • 家系図
    • Union-Find木
      • グループ分け
• グラフ
  • 頂点と頂点同士の関係を表したデータ構造
  • 種類
    • 無向グラフ
      • facebook
    • 有向グラフ
      • twitter

数値計算

• エラトステネスの篩
  • n以下の素数を求めるアルゴリズム
    • 1を消す
    • 2で割り切れるものを消す
    • これを√nまで繰り返す
    • 残ったものが素数
• ユークリッドの互除法
  • 最大公約数を求めるアルゴリズム
    • a % b = r (a = 15, b = 12, r = 3)
    • a = b, b = r(a = 12, b = 3, r = 0)
    • r = 0ならbが最大公約数(b = 3)

数学

• 和の公式
  • 1...nの総和を求める公式
  • n * (n + 1) / 2
• 因数分解
  • 和や差の式を積の式に変換すること
  • (ma + mb) = m(a + b)
• フィボナッチ数列
  • 2つ前の項と1つ前の項を足してできる数列
  • 1, 1, 2, 3, 5, 8, 13, 21, ...
• 3点が同一直線上の点であることを調べる
  • dx2 * dy1 = dx1 * dy2
    • A(2, 3), B(7, 6), C(12, 9)の場合
      • dx2 * dy1 = (Cx - Ax) * (By - Ay) = 10 * 3 = 30
      • dx1 * dy2 = (Bx - Ax) * (Cy - Ay) = 5 * 6 = 30
      • dx2 * dy1 = dx1 * dy2 なので同一直線上の点である
    • A(-1, -1), B(0, 1), C(1, 3)の場合
      • dx2 * dy1 = (Cx - Ax) * (By - Ay) = 2 * 2 = 4
      • dx1 * dy2 = (Bx - Ax) * (Cy - Ay) = 1 * 4 = 4
      • dx2 * dy1 = dx1 * dy2 なので同一直線上の点である
    • A < B < Cでなくても当てはまる
• 最小公倍数
  • a * b / gcd(a, b)
• 線分の長さ
  • ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
• 共通区間の長さ
  • max(0, min(r1,r2) - max(l1, l2))

その他

• 動的計画法
  • 対象となる問題を部分分割し、部分問題の結果を記録しながら問題を解決する方法
  • 関連問題
    • 階段問題
    • ナップサック問題
    • 部分和問題
    • ハノイの塔
• バックトラック法
  • 条件に一致するものがない場合に、一つ前に戻って別ルートに行くことを繰り返して検索を行う方法
  • 関連問題
    • 8クイーン問題
• 貪欲法
  • 最適解が得られるかはわからないが、その場での最善を選ぶ方法
  • 関連問題
    • コイン問題
• 累積和
  • 配列に対して前処理をしておくことで区間の総和を早く求める方法
    • [1, 2, 3, 4, 5] -> [0, 1, 3, 6, 10, 15] // 前処理
    • 3~5の総和を求めたい場合
      • [3 + 4 + 5] = 12
        • 要素に対して毎回足し算して求める必要がある
      • [15 - 3] = 12
      • 適切に前処理しておけば区間を指定するだけで総和が求められる