「アルゴリズム図鑑」を読んだので、その要点

読書感想文です。
[アルゴリズム図鑑 絵で見てわかる26のアルゴリズム | 石田 保輝, 宮崎 修一 |本 | 通販 | Amazon](https://www.amazon.co.jp/dp/4798149772)

![](https://images-fe.ssl-images-amazon.com/images/I/51Igz5EAVfL._SX218_BO1,204,203,200_QL40_ML2_.jpg)

https://www.shoeisha.co.jp/campaign/book/algorithm/


## 感想

- 逆引きもできると嬉しい。こういうことをしたいときにどれを選ぶと良いのか。
- プログラミング言語は出てこないので、自分の好きな言語と合わせて使うのが良い。という意味ではこの本だけでは足りないかもしれない。
- プログラミング言語を学びつつ
    - 「こういう問題のときにはこのアルゴリズムが使えそう」と当たりをつけた上で
        - この本に登場してくる図を見て、こういう解法になるね、というステップで使う、のか。
- いずれにしても用語の整理には良いかも。図鑑なので頭からお尻まで読みきらなくても、思い出したときに引けばよいのかもしれない。

### 序章　アルゴリズムの基本
- 0-1　アルゴリズムとは？
    - 計算や作業を遂行するための手順
    - 「プログラム」はプログラミング言語で書かれたもの。アルゴリズムはその前段階。
- 0-2　計算時間の測り方
    - ステップ数
    - 1ステップとは、「計算を終了するまでに基本単位を何回実行したか」

### 第1章　データ構造
- 1-1　データ構造とは？
    - 例: 上から順
    - 例: 五十音順
- 1-2　リスト
    - リスト: データ構造の一つで、データを一直線に並べた構造
        - 追加や削除が簡単
        - アクセスに時間がかかる
- 1-3　配列
    - 配列: データ構造の一つで、データを1列に並べるもの
        - [今更聞けない配列とリストのデータ構造 - Qiita](https://qiita.com/maimax/items/dcff7206b747bf726ad8)
        - データへのアクセスは簡単
        - 追加や削除にはコストがかかる
            - 電話帳のイメージ
- 1-4　スタック
    - データを1列に並べるが、新しく追加したデータからしかアクセスできない
        - 書類を一番上に起き、一番上から取り出すイメージ
- 1-5　キュー
    - データを1列に並べるが、追加する側と削除する側が反対。
        - 待ち行列のイメージ
- 1-6　ハッシュテーブル
    - KeyとValue のセット
    - ハッシュ関数を利用できる
- 1-7　ヒープ
    - グラフの木構造
    - プライオリティキューを実現するときに使われる
- 1-8　2分探索木
    - 各ノードにデータが格納される

### 第2章　ソート
- 2-1　ソートとは？
    - 数字を小さい順に並び替える
    - 入力として与えられた数字を小さい順に並べ替える
- 2-2　バブルソート
    - 右から左に向かって隣り合う2つの数字を比較して入れ替える
    - [『アルゴリズム図鑑』のアルゴリズムをPython3で実装(バブルソート編) - Qiita](https://qiita.com/smalltech/items/63d50803c83a31c6815e)
- 2-3　選択ソート
    - 数列の中から最小値を検索し、左端の数値と入れ替える
    - [『アルゴリズム図鑑』のアルゴリズムをPython3で実装(選択ソート編) - Qiita](https://qiita.com/smalltech/items/e54709bfdcf33e5f2bb8)
- 2-4　挿入ソート
    - 数列の左側から順番にソートする
    - 最初に取り出した数字をその左の数字と比較する
- 2-5　ヒープソート
    - データ構造のヒープを利用する
    - [『アルゴリズム図鑑』のアルゴリズムをPython3で実装(ヒープソート編) - Qiita](https://qiita.com/smalltech/items/af16d278d2f0c8491658)
- 2-6　マージソート
    - 分割、マージ、ソートする
- 2-7　クイックソート
    - pivot という基準になる数を選び、それより小さい数か大きい数のそれぞれのグループに分け、それらをソートする。
    - アルゴリズムの内部にアルゴリズム自身を使う「再帰」

### 第3章　配列の探索
- 3-1　線形探索
    - 配列からデータを探索する
    - 前から順番にデータを調べていく
- 3-2　2分探索
    - 配列からデータを探索する
    - データがソートされている場合にのみ適用できる
    - 配列の真ん中あたりのデータと目的のデータを比較する

### 第4章　グラフ探索
- 4-1　グラフとは？
    - ここでは、頂点がいくつか合って、いくつかの頂点ペアが辺で結ばれているもの
    - 路線図中から経路を見つけるなど
- 4-2　幅優先探索
    - グラフを探索する
    - 頂点を探索する際、視点に近い頂点から優先的に探索していく
- 4-3　深さ優先探索
    - 頂点を探索する際、1つの道を行けるところまで進んでいき、これ以上進むことができなくなったところで引き返し、次の候補を進んでいく
- 4-4　ベルマン-フォード法
    - グラフの二点間の最短距離を求める
- 4-5　ダイクストラ法
    - 間を通る辺のコストの総和が最も小さいものを求める
    - [ベルマンフォード法とダイクストラ法の概念を完全に理解する - Qiita](https://qiita.com/ko-ya346/items/359a3e03c5e20b04c573)
- 4-6　A* (エースター)
    - ダイクストラ法を更に発展させたもの

### 第5章　セキュリティのアルゴリズム
- 5-1　セキュリティとアルゴリズム
- 5-2　暗号の基本
- 5-3　ハッシュ関数
- 5-4　共通鍵暗号方式
- 5-5　公開鍵暗号方式
- 5-6　ハイブリッド暗号方式
- 5-7　ディフィ-ヘルマン鍵交換法
- 5-8　メッセージ認証コード
- 5-9　デジタル署名
- 5-10　デジタル証明書

### 第6章　クラスタリング
- 6-1　クラスタリングとは？
    - 多数のデータが与えられたときに、それを似た者同士に分類する
- 6-2　k-means法

### 第7章　その他のアルゴリズム
- 7-1　ユークリッドの互除法
- 7-2　素数判定法
- 7-3　ページランク
- 7-4　ハノイの塔


後半は目次引用のみ。キーワードとして知っておけば良いかなという感想。

## 余談・参考

[しめじソートが人気なので解説してみる - プログラマのつれづれなるままに](https://www.timbreofprogram.info/blog/archives/633)
[しめじソート | たまちのブログ](https://ameblo.jp/tamati17/entry-12699120974.html)
[▽しめじソート▽100グラムにちょうせん! - ピタゴラスイッチ - NHK](https://www.nhk.jp/p/pitagora/ts/WLQ76PGNW2/episode/te/VR78NG1KLW/)

[8時間を0.01秒に短縮　「アルゴリズムの素晴らしさが2分で分かる動画」が今すぐ勉強したくなる分かりやすさ（1/2 ページ） - ねとらぼ](https://nlab.itmedia.co.jp/nl/articles/2204/14/news034.html)
[30 分でわかる！アルゴリズムの基本 - Speaker Deck](https://speakerdeck.com/e869120/30-fen-dewakaru-arugorizumufalseji-ben)


以上です～