【まとめ】アルゴリズム的思考力が身につく！Atcoder ②
アルゴリズムの勉強のために以下の本を読んだので、読んでいた時のメモ
上級編
中級編は前記事
再帰関数と全探索
関数の中で同じ関数を呼び出す関数
終了条件必ずつける
N重のfor loop→コード書くのが難しい
→同じ処理(つまり再帰関数)をfor i in Nすればいいよね。
ナップザック問題
重さWの中で品物の価値の和を最大化する問題
品物を選ぶか選ばないかを0,1で表して0と1の数列を作ると、2^N乗通りの計算が必要となる
N重のfor文はNが確定してないと書けない
→再帰関数 or itertools.product(Python3)
0,1だけで表される数列は2進数とも取れる→bit全探索
幅優先探索(BFS)
グラフの始点に近いところから探す探索方法
幅優先を使うと、始点からある頂点までの最短経路が探せる
使うデータ
- que: キュー これから探索する予定の頂点
- dist: 配列 探索終了時では、dist[v]は始点から頂点vへの最短経路 長さはグラフの頂点数N
キューは、Fist in Fist Out(FIFO)
→最初にqueに入れた(始点に近い)頂点から先に取り出す(幅優先！)
グラフの辺の数をMとすると、計算量はO(M)
ダイクストラ法
BFSは頂点間の距離がすべて等しい場合に使える。
等しくない場合にはダイクストラ法が使える。
BFSを拡張して優先度付きキューにすると、ダイクストラ法になる
動的計画法(DP)
グラフの各辺に重みを付けたグラフ→ 重み付きグラフ
重み付きグラフの場合は、幅優先探索よりも動的計画法を使う
再帰関数で全探索
→ 同じ再帰関数rec(i)を何度も計算しているのが無駄
→ 同じ計算は2度しないようにメモしておく(キャッシュ)
→ 動的計画法dp[i]＝rec(i) 答えをメモ！
貪欲法
Nステップからなる意思決定を最適化
→ 一般的には動的計画法が使われる
→ 各ステップの最善の選択を繰り返す方法もある(貪欲法)
しかし、将来的に最適になる選択を切り捨てている可能性があるため、貪欲法が常に最適とは限らない
→ どのような場面で貪欲法が使えるかを見極めるのが大切
以下のような構造の時で有用
- 交換しても悪化しない
- 後によいものを残す
- 端から決まっていく
Discussion