四十三庵

蔀の雑記帳

アルゴリズム設計法

目次

brute force solution

  • 日本語の訳語がない
  • セキュリティの文脈ではよくブルートフォースアタックが使われる
  • 訳をあてるとしたら「粗雑解」とかがいいかな
  • 「とりあえず総当たりで……」「とりあえずループを全部回して全部条件分岐させて……」など、計算効率を考えずに書くアルゴリズム
  • 解決策としては愚策だけれど、最初の一歩としてはとりあえず良い
    • 最初から洗練されたアルゴリズム設計はできないし、粗雑でも解法をつくることで課題が具体的になる効果もある
  • また、対象のデータサイズが小さければ、brute force solutionで十分な場合もある

Dynamic Programming Solution(動的計画法)

  • 対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法

  • SAC

  • Qiita

分類

  • ナップサック DP
  • 区間 DP
  • bit DP

Divide and conquer solution (分割統治法)

  • 大きな問題を小さく分解していくことで、計算効率を高める

Greedy Method(欲張り法)

  • 局所的な最適解を求めるためのアルゴリズム設計法
  • 前提が変わると上手くいかないが、その前提が機能する状況においては計算が早い場合がある
  • 例) ダイクストラのアルゴリズム(Dijkstra Algorithm)はコストが負の値になると正しい最短経路が出せない