【技術勉強】アルゴリズム図鑑

データ構造

スタック

後かから入れたものを、先に出す
LIFO(Last In First Out)

キュー

先に入れたものを、先に出す
FIFO(First In First Out)

ハッシュ関数

ヒープ

f:id:naaaaaaa-tooo:20190612204632j:plain

各「ノード」は、最大2つの子データをもつ
子データは、親データより大きなもの

「プライオリティキュー」=自由に追加でき、小さいものから取り出す
最小値を頻繁に出すときに使える

二分探索木

https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png

各「ノード」は、最大2つの子データをもつ
全てのノードは、そのノードの左部分木に含まれるどの数よりも大きくなる
全てのノードは、そのノードの右部分木に含まれるどの数よりも小さくなる



ソート

バブルソート

右から左に向かって、隣り合う2つの数字を比較して入れ替える
それを終わるまで繰り返す

選択ソート

数列の中から最小値を探し出し、左端の数字と入れ替える

ヒープソート

マージソート

https://camo.qiitausercontent.com/51561df3442f3cdd7d2ab40caab47964bf2eb0cb/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f3138323936332f62616665663162332d373139632d626337332d633937362d3932326566636332613331662e6a706567

ソートする数列をほぼ同じ長さの2つの数列に分割していって、分割できないところまで行ったら、グループ同士をマージしていっていく

クイックソート

https://slidesplayer.net/slide/11273690/61/images/20/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88%E3%81%AE%E5%8E%9F%E7%90%86+%E3%82%BD%E3%83%BC%E3%83%88%E3%81%99%E3%82%8B%E7%AF%84%E5%9B%B2%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%81%8B%E3%82%89%E9%81%A9%E5%BD%93%E3%81%AA%E8%BB%B8%E8%A6%81%E7%B4%A0%28%E6%9E%A2%E8%BB%B8%E3%80%81pivot%29+X%E3%82%92%E9%81%B8%E3%81%B6%E3%80%82.jpg

数列の中から、基準となる数字を取り出して、それより大きいか、小さいか振り分けていく



配列の探索

線形探索

二分探索

https://www.codereading.com/algo_and_ds/algo/images/binary-search.png



グラフ探索

幅優先探索

https://image.itmedia.co.jp/enterprise/articles/1001/16/tnfig1.jpg

深さ優先探索

https://camo.qiitausercontent.com/b30f025fc244e9706faa04e1c254a59aac357aa4/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f3134303330342f64343138303762322d396238642d333833642d376463662d3161613537613837396133362e706e67



セキュリティ

ハッシュ関数

特徴

  1. 出力する値のデータ長が変わらない

  2. 同じ入力は必ず同じ出力になる

  3. 似た入力でも1ビット違えば、出力は大きく異なる

  4. 全く別の入力をしても、同じハッシュ値になる可能性がある =「ハッシュ値の衝突」

  5. ハッシュ値から元のデータを逆算することができない

パスワードをデータベースに保存するときとかに使われる。

共通鍵暗号方式

暗号と復号に同じ鍵を用いる方式
問題点:共通鍵を相手に送る場合、盗聴される危険性がある

公開鍵暗号方式

暗号化と復号で異なる鍵を使う方式
暗号化に使う鍵を「公開鍵」
復号に使う鍵を「秘密鍵

公開鍵を相手に渡して暗号化してもらえば、
三者に公開鍵を盗聴されていても、公開鍵ではデータを復号できないため、
共通鍵暗号方式より安全性がある

しかし、もらった公開鍵は、果たして公開鍵をくれた本当の人物かどうかわからない点や、
暗号化の処理速度が遅いという問題点がある

ハイブリッド暗号方式

共通鍵暗号方式と公開鍵暗号方式を組み合わせたもの

AからBにデータを送ろうとする場合

  1. Aが処理速度の早い共通鍵暗号方式でデータを暗号化する

  2. Bが公開鍵と秘密鍵を作成する

  3. BがAに公開鍵を送信

  4. Aはその公開鍵を使って、共通鍵暗号方式に使う鍵を暗号化する

  5. AからBに暗号化した鍵を送信する

  6. Bは秘密鍵を使って、鍵を復号する

  7. AからBに暗号化したデータを送り、それをBが復号した共通鍵を使って復号する

SSLでこの方式が使われている



その他

ユークリッドの互除法