けんちょん本メモ
bayamasa解答はこちら https://github.com/drken1215/book_algorithm_solution/tree/master/solutions
二分探索法
「真ん中で切ってどちらかに絞っていく」
線形探索法
「上から順番に絞っていく」
ex)
年齢当てゲームにおいて年齢が20~38歳だとわかっている場合
二分探索法
- 28未満か？ →仮にYes
- 24未満か？(このように常に真ん中で区切っていく)
線形探索法
- 20歳か？
- 21歳か？(このように範囲の最初の部分から聞いていく)
年齢当てゲームのような答えが範囲のどこにあるかわからない場合には、
二分探索法の方が計算量が早い
bayamasa深さ優先探索(depth-first search)
値を決め打ちして突き進み、もしエラーが出力された場合には一歩もどって次の選択肢を試す方法
bayamasa幅優先探索(breadth-first search BFS)
幅優先探索は探索を開始する頂点からの距離（深さ）が等しくなるように進んでいく方式で、出発点の隣接ノード（距離1）をすべて調べ、隣接ノードの隣接ノード（距離2）をすべて調べ、そのまた隣接ノード（距離3）を…という手順を終了まで繰り返す。
bayamasa1秒間で処理できる計算ステップ回数の目安
大体今のコンピュータだったら10^9回くらいの計算を行う事が可能
bayamasaランダウ記法
あるアルゴリズムT(N)があるときに、それをP(N)で割った値の絶対値がc以下になる場合
T(N) = O(P(N))が成り立つ
つまり |T(N)/P(N)| <= cになる場合、O(N)で表される。
ex)
T(N) = 3N^2 + 5N + 100の計算時間だとする
P(N)をN^2だとすると、 T(N) / P(N) = (3N^2 + 5N + 100) / N^2 = 3 + 5/N + 100/N^2
これが成立する。
その場合、3 + 5/N + 100/N^2 <= 4となるのでT(N)/P(N)となる整数が存在する。
このためT(N) = O(N^2)となりT(N)はN^2の計算量を概算出来る。
bayamasa第三章
全探索
アルゴリズムの方法として、考えられる場合を全て調べ上げるということで、
原理的にはすべての問題を解決することが出来る。
タイムアウトが発生するようなアルゴリズムにおいても計算量によっては問題がない場合が多々あるので、
そのような場合は全探索は非常に有効なソリューションになる。
bayamasa線形探索法(linear search method)
線形探索法とは１つ１つの要素を順番に調べていくという探索法です。
ex) 数列a=(4, 3, 12, 7, 11)の中に、値 v = 7 が含まれているかどうかを求めよ
線形探索法は添字、つまりインデックスの取得などにも役立つ。
上記の例で、値が含まれている場合のif条件文を付け足すことにより、何番目に含まれているのかを確認することが出来る。
bayamasa部分集合のアルゴリズム
整数の２進法表現
N個の正の整数と正の整数Wが与えられたときに、N個の整数の中からいくつか選んで総和をとることでWになるような整数が存在するかどうか判定せよ
N個の整数からなる集合の部分集合は2^N通り存在する。(←証明したい
それを全探索で表現する。
2^Nなので、2進数を利用する。
N=8のとき、部分集合の通りは2^8で表される。
つまり、2進数の8bitで表される。
その時の式は、bit & (1 << i)
これでiが判定できるので部分集合を合計するので、総和が存在するかどうか求める事ができる。
bayamasa数列の中で２番めに小さい値を求める問題
- 変数を２つ定義する(一番小さい値、二番目に小さい値)
- 線形リストで探索する
- もし一番小さい値が来た場合は、一番小さい値を更新して元々一番小さい値に入っていたものを二番目に小さい値に入れる
- もし二番目に小さい値が来た場合は二番目に小さい値を更新する
- 3と4はif-elseifで結合してどちらの条件にも含まれる場合は除外するようにする
bayamasa数列の中から2つ選んで差分を取ったときの最大値をO(N)で求められるアルゴリズムを設計せよ
2つの値の差分が一番大きい→その数列の中の最大値と最小値を求めればよい
bayamasa再帰関数のテンプレート
if(ベースケース){
return ベースケース;
}
以上のようにベースケースを設置して、そこに向けて値を計算していく方法が再帰関数である。呼び出しが無限に行われてしまうことを防ぐ事ができる。
bayamasaユークリッドの互除法
2つの整数m, n があるときにmを割った余りが存在しないときに、その商が最大公約数と一致する。
もし余りが存在した場合、mとnの中で低い方の数で余りを割ることにより、上記条件と同じ条件が成り立つ。
つまり余りがでなくなるまで割り切っていくことにより、最大公約数が計算できるということ。
bayamasaメモ化
同じ内容を計算する計算量をメモを使うことによって省略する。
配列と再帰関数を使う事によって、値をキャッシュする
bayamasa分割統治法
問題を分割していく手法。
N個の整数についての問題を、N-1の2つの小問題に帰着させ、それをN-3に関する4つの小問題にしていく。
このように問題を各部分に分けていき、それを再帰的に解く手法を分割統治法と呼ぶ。
分割統治法のメリットはアルゴリズムを高速にする場面です。
ある完成したアルゴリズムの計算量の大きすぎてタイムアウトになる場合、分割統治法を用いた計算は非常に有用です。
bayamasa動的計画法
与えられた問題全体を一連の部分問題に分解して、各部分問題の解をメモ化しながら、
大きい部分問題の解を求めていく手法。
手法が普遍的で、分野横断的なものなので実問題を解決するための実践的なアルゴリズムに最も近いと言える
bayamasa緩和
値を比較して、小さい値を配列などに格納していく処理
C++では緩和処理を実現するための関数chminなどを用意しておくとよい。
template<class T> void chmin(T& a, T b){
if(a > b){
a = b;
}
}
配列における、二分探索の計算量は配列の要素数に着目する。
配列の要素数が1024のとき、つまり2^10のときは二分探索により毎回配列が半分になっていく
であれば、計算量は10となる。
つまり配列要素数NがN = 2^kで表される場合、計算量はlogNとなる。
bayamasa貪欲法
適当な基準を用いて、局所的に最適なケースを連続して選択する
つまり、具体的な値を当てはめていき、値を求めていくアルゴリズム
動的計画法をより具体化したもの。