【技術勉強】アルゴリズム図鑑
データ構造
スタック
後かから入れたものを、先に出す
LIFO(Last In First Out)
キュー
先に入れたものを、先に出す
FIFO(First In First Out)
ハッシュ関数
ヒープ
各「ノード」は、最大2つの子データをもつ
子データは、親データより大きなもの
「プライオリティキュー」=自由に追加でき、小さいものから取り出す
最小値を頻繁に出すときに使える
二分探索木
各「ノード」は、最大2つの子データをもつ
全てのノードは、そのノードの左部分木に含まれるどの数よりも大きくなる
全てのノードは、そのノードの右部分木に含まれるどの数よりも小さくなる
ソート
バブルソート
右から左に向かって、隣り合う2つの数字を比較して入れ替える
それを終わるまで繰り返す
選択ソート
数列の中から最小値を探し出し、左端の数字と入れ替える
ヒープソート
マージソート
ソートする数列をほぼ同じ長さの2つの数列に分割していって、分割できないところまで行ったら、グループ同士をマージしていっていく
クイックソート
数列の中から、基準となる数字を取り出して、それより大きいか、小さいか振り分けていく
配列の探索
線形探索
二分探索
グラフ探索
幅優先探索
深さ優先探索
セキュリティ
ハッシュ関数
特徴
出力する値のデータ長が変わらない
同じ入力は必ず同じ出力になる
似た入力でも1ビット違えば、出力は大きく異なる
ハッシュ値から元のデータを逆算することができない
パスワードをデータベースに保存するときとかに使われる。
共通鍵暗号方式
暗号と復号に同じ鍵を用いる方式
問題点:共通鍵を相手に送る場合、盗聴される危険性がある
公開鍵暗号方式
暗号化と復号で異なる鍵を使う方式
暗号化に使う鍵を「公開鍵」
復号に使う鍵を「秘密鍵」
公開鍵を相手に渡して暗号化してもらえば、
第三者に公開鍵を盗聴されていても、公開鍵ではデータを復号できないため、
共通鍵暗号方式より安全性がある
しかし、もらった公開鍵は、果たして公開鍵をくれた本当の人物かどうかわからない点や、
暗号化の処理速度が遅いという問題点がある
ハイブリッド暗号方式
AからBにデータを送ろうとする場合
Aが処理速度の早い共通鍵暗号方式でデータを暗号化する
Bが公開鍵と秘密鍵を作成する
BがAに公開鍵を送信
Aはその公開鍵を使って、共通鍵暗号方式に使う鍵を暗号化する
AからBに暗号化した鍵を送信する
Bは秘密鍵を使って、鍵を復号する
AからBに暗号化したデータを送り、それをBが復号した共通鍵を使って復号する
SSLでこの方式が使われている