5章　動的計画法

ナップサック問題

• この表がわかりそうでわからない
• i番目の品物を選ぶとき、選ばなかったときで価値が高い方で埋めていくという全探索何だと思う

編集距離

• 編集距離は２つの文字列S, Tの類似度を測るもの。

• 以下のようなテーブルを作成する

• 編集コストが発生するのは文字の変更、削除、挿入時です。
• 計算量はO(|S||T|)

区間分割

感想

• N個の数列においてdpテーブルを作成することで解決できそうな問題は動的計画法を疑う
• dp[i]のようにi番目の要素に対して考えればいいこともあれば、dp[i][j]のように要素を追加する必要がある問題もある
• が、基本はdpテーブルを作成すること。
• Flog問題、ナップサック問題はまあ何となく解説みれば理解できたが編集距離に関してはいまいちピンとこない。編集距離問題はシンプルに編集コストの最大、最小を求めるような問題であれば理解できそうだが類似問題がピンとこない。
• 区間分割は[i, j]の区間に対して考える。

6章　二分探索

• ある配列などからある値を探索するアルゴリズム
• だけでなく、i番目の条件を満たす範囲を二分探索で範囲を狭めていくみたいな使い方もできる

7章　貪欲法

• 目先の最適な条件を順に試していく
• 直感的

8章　データ構造

配列

• i番目の要素へのアクセスは非常に高速。O(1)
• JavaのArrayListやGoのSliceは内部的に配列でデータを保持しているのでアクセスはO(1)
• 連結リストと呼ばれるようなものはO(N)になる可能性がある。JavaのLinkedListなど
• 配列は要素の削除やある要素の次に任意の値を追加するなどの操作はO(N)になる。
• これは、配列の順番が変わるため順番を割り振り直すのにO(N)の計算量が必要。

連結リスト

• 配列の弱点である要素の挿入・削除が高速に実行できる
• 内部的な実装は各要素(Node)が次の要素や前の要素のポインタを持っているイメージ
• なので、ポインタの向きを基本的には変えるだけでいいので配列よりも高速になる
• JavaではLinkedListとしてある。Goでもcontainer/listという標準パッケージがあるみたい。

配列と連結リストの比較

• 大抵の用件は配列で事足りる
• i番目の要素へのアクセスと最後尾への要素の追加がほとんどのケースが多いから
• 配列であればこれらはO(1)の計算量で高速に実行できる
• もし、要素の削除や特定の位置への挿入などを頻繁に行うようなデータ構造が欲しい場合に連結リストは活用できる。
• 要素を検索する場合、配列でも連結リストでも線形探索を用いればO(N)の計算量になってしまう。
• 要素の検索などを高速で実行したい場合、ハッシュテーブルや平衡二分探索木が使える

ハッシュテーブル

• T[x]データ構造中に値xが存在するかどうかを表す値(trueまたはfalse)
• このうようなデータ構造のとき、要素xの挿入、削除、検索はT[x]の値であるBool値の参照、更新操作のみのためO(1)という高速な処理ができる
• そのかわり、インデックスや順序を保つためのポインタなどは持っていないので順序は保証することはできない。
• このような配列T[x]をバケットといったりする
• バケットだとxがx以上M未満の整数値に限られてしまうため汎用性に欠ける
• そこで、汎用性を持たせたものがハッシュテーブル
• ハッシュテーブルでは整数に限らない一般的なデータ集合Sの各要素xに対して0<=h(x)<Mを満たす整数h(x)に対応させることを考える
• このとき、h(x)をハッシュ関数とよぶ
• また、xのことをキーとよび、ハッシュ関数の値のことをハッシュ値と呼ぶ。
• どのキーに対してもハッシュ値が異なる、つまりハッシュ値の衝突が起こらないときのハッシュ関数を完全ハッシュ関数とよぶ。
• この完全ハッシュ関数を設計できたならば、どのようなデータ形式でもハッシュ値に変換し、そのハッシュ値をキーに高速に要素の追加、削除、検索ができるはず。これがハッシュテーブルの内部構造
• ただし、ハッシュの衝突を避けるのは困難。
• ハッシュの衝突対策としてh(x)=h(y)のように衝突が起こった場合、ハッシュテーブル内部ではh(x)とh(y)が連結リストで結びついた状態で保存される
• 計算量はO(1 + α)となり、αは負荷率とする。この負荷率はハッシュテーブルの振る舞いを示す指標で、α = 1/2くらいだと、十分O(1)の計算量が達成できるらしい
• JavaのSetとかがハッシュテーブルを活用してる

連想配列

• 整数値ではなく文字列のような値をキーに値を紐づけたようなデータ構造のこと
• これはハッシュテーブルをもちいることで実現できる
• たぶん、キーとなる値をハッシュ値としてキーにし、それに対応する値も指定できるようにしただけ。従来のハッシュテーブルはハッシュ値をキーにして真偽値を対応させていたのでそれを汎用的なデータ型に変えただけ、たぶん

12章　ソート

• 同じ値を持つ要素をソートしたときに順序を保たないことがある。これをソートの安定性という
• 挿入ソートのような外部メモリをほとんど使用しないアルゴリズムをin-placeであるという。

挿入ソート

• 左からi枚がソートされている状態からi+1枚がソートされている状態にするソート方法
• i+1枚目の要素を適切な場所にソートしていくアルゴリズムなので挿入ソート
• 最悪時の計算量はO(N^2)
• これは、ソートしたい順序と逆に整列している時が最悪時になる
• 挿入ソートは安定ソートでin-placeである

マージソート

• 分割統治法を活用したソート
• 計算量はO(NlogN)
• とりあえず左と右に半分に分割する
• 再起的に全部整列させる
• そのあとに、左と右のソート結果をコピーしておく(右は左右反転)
• あとは左と右を見ていい感じに併合していく
• 分割と併合がO(logN)の計算量を必要とし、それぞれの段階における併合作業にO(N)ずつの計算量を要するためマージソートはO(NlogN)
• また、マージソートは一旦左と右のソート結果をコピーするため外部メモリを必要とするためin-place性は満たしていない。

クイックソート

• クイックソートはマージソート同様、配列を分割しそれぞれを再帰的に解いてまとめる分割倒置法にのっとったアルゴリズム
• 配列の中から適当に選択された要素(pivot)を起点に分割し、それぞれを再帰的に考える
• クイックソートの最悪時間計算量はΘ(N^2)だけど、実用上はマージソートよりも高速に動作するといわれている。

ヒープソート

• ヒープを用いたソートだよ

バケットソート

• クイックソートやヒープソートのようなソートは比較ソートアルゴリズムといえる
• バケットソートはソートしたい配列aの各要素値は0以上A未満であるという仮定の下では計算量はO(N+A)となる

13章　グラフ探索

• 全頂点をseen、探索予定の頂点の格納先をtodoとして
• todoをstackもしくはqueueとして取り出して検索していく
• このときstackとして探索するのを深さ優先探索(dfs)、queueを**幅優先探索(bfs)**という
• また、深さ優先探索は再帰関数と相性がいいので再帰関数で実装することもできる
• 幅優先探索は最短経路探索ともとれる
• dfsもbfsも計算量はO(|V| + |E|)となるらしい。Vは頂点数、Eは辺の数

s-tパスを求める

• ある頂点sから頂点tにたどりつくようなパスが存在するかという問題
• dfsでもbfsでも解ける
• 探索済みにtがあるかどうかで判定

二部グラフ判定

• 白色と黒色で頂点を塗ることを考える
• このとき、隣接した頂点が同色になってないようなグラフを二部グラフという

トポロジカルソート

• 有向グラフに対し、各頂点を辺の向きに沿うように順序つけて並び替えること。
• 有向サイクルを含む有向グラフではトポロジカルソートはできない
• トポロジカルソート可能な有向グラフをDAGというよ
• トポロジカルソートは深さ優先探索における再帰関数を抜けた順序に頂点を並べ、それを逆順に並べ直すことでソート順が得られる

14章　最短路問題

最短路問題の整理

• 重みなしグラフであればbfsで
• DAGであれば動的計画法がつかえる
• 辺の重みが全て非負なグラフであればダイクストラ法
• 負の重みの辺も含むグラフであればベルマン・フォードマン法が使える

AtCoder メモ

• 周遊パスD枚セットをkセット買えばN日全て周遊パスを使えるみたいなとき、以下のようにするとkを求めることができる

k = n + d - 1 / d