20210301~06_アウトプット（アルゴリズム）

3/1行ったこと 8時間30分

• SQL問題文をひたすら解く。

3/2行ったこと 2時間30分

• SQL問題文をひたすら解く。

3/3行ったこと 1時間30分

• アルゴリズム本を読む（インプット）

3/4行ったこと 4時間30分

• プロを目指す人のためのRuby入門

3/5行ったこと 3時間35分

• プロを目指す人のためのRuby入門
  
  

3/6行ったこと 18時間

• アルゴリズム実技検定公式テキスト
  
  

新しい発見

アルゴリズムとは

• 「入力値」👉「手続き・処理」👉「出力値」

• 上記において、どのような「入力値」であってもその「手続き・処理」によって所望の結果を「出力値」として得られるようにすることが大事。

• そのための定式化・抽象化された問題を解くための手続きをアルゴリズムという。

• 一見違う問題（課題）のように思えても、抽象化した際、同じ構造であれば解決に導くことができる。

• ソフトウェアの特定分野だけでなく全ての分野に共通する問題の解き方を学ぶことができるメリットがある。

• 良し悪しの基準として「計算時間（計算を終了するまでに基本単位を何回実行したか」がある。

データ構造とは？

データをコンピュータのメモリに蓄える時の、データの順番や位置関係を規定したもの。

NO	データ構造	内容	メリット	デメリット
1	リスト	データを一直線に並べた構造	追加や削除がしやすい	アクセスに時間がかかる
2	配列	データを一列に並べた構造	アクセスがしやすい	追加や削除にはコストがかかる
3	スタック	１列に並べた構造。新しいデータは一番上に追加（プッシュ）され、取り出す際（ポップ）は一番上から処理されていく。	常に最新のデータにアクセスしたいときは便利	古いデータにアクセスする時にコストがかかる
4	キュー	１列に並べた構造。行列と同じように新しいデータは一番後ろに追加（エンキュー）され、一番前から処理（デキュー）されていく。	古いものから順番に処理できる	必要なデータが出てくるまでデキューする
5	ハッシュテーブル	キーとバリューをセットにしたものをデータとして格納	データ検索しやすい	キーとバリューを入れる箱を大きくしすぎるとメモリの無駄遣いになる
6	ヒープ	木のような構造の一つ。最小値から順に選ばれる	データ数に関係なく常に一番上に最小値がある	計算時間は木の高さに比例する
7	２分探索木	木のような構造の一つ。各ノード（頂点）は最大２つの子を持つ。２つに分けた左側の塊はノードよりも数は小さくなり、右側の塊はノードよりも数が大きくなる性質がある	大小の比較だけでデータ検索や適切な位置へデータ追加できる	木のバランスが悪い（高くなる）と計算時間がかかる。

ソートとは？

小さい順に並び替えること。

NO	ソート	内容	注意点
1	バブルソート	右から左に向かって、隣あう２つの数字を比べて入れ替える	数字の入れ替え回数が入力データの状況に依存する（たまたま小さい順に並んでたら早く終わる、逆も然り）
2	選択ソート	数列の中から一番小さい値を探して左端の数字と入れ替えること	最小値を最初に探す
3	挿入ソート	数列の左側から順番にソートしながら確定させていく（その場合右側が未探索領域）	1のバブルソートと同じく、状況に依存。
4	ヒープソート	データ構造のヒープを利用して、小さいものから格納。大きいものから取り出して右から並べるとソートできる	上記1・2・3に比べて高速になるが実装は複雑になる
5	マージソート	ソートしたい数列をほぼ同じ長さの２つの数列に分解していく。これ以上分割できなくなったところから、並び替えしながら段々にマージしていく。	4のヒープソートと同じく高速だが複雑。
6	クイックソート	ピポットと呼ばれる基準となる数字を数列からランダムに１つ選ぶ。そして①ピポットより小さい数②ピポット③ピポットより大きい数に分けてそれぞれソートしてからまたくっつける	運悪く最小値がピポットとして選ばれてしまうと力を発揮できない

グラフとは？

• マルで書かれた頂点（ノード）と、それらを結ぶ辺で構成されたもの。

• 辺を結ぶ順番が決まっていることを「有向グラフ」という。（逆は「無向グラフ」）

探索方法

NO	探索方法	内容	備考
1	幅優先探索	始点に近い点から優先的に探索する方法。辺の重みは全て同一。	データ構造は先入れ先出しのキューを用いる
2	深さ優先探索	１つの路を行けるところまで掘り下げていき、これ以上進むことのできないところで引き返して次の路を探していく方法。辺の重みは全て同一。	後入れ先出しのスタックを用いる
3	ベルマン・フォード法	辺に重みをつけて「始点」と「終点」を決める。その間のコストの総和が最も少ないものを探す方法。全ての辺のコスト計算をしてから最短を決める。	負のコストが入っていても正しく計算できる
4	ダイクストラ法	3と同じ。違うところは、頂点からの辺の重みの候補をその都度決定して先に進むこと（なので全ての辺のコストは計算しない）	負のコストを含むグラフには使用できない
5	A*（エースター）	ダイクストラ法を発展させたもの。予め推定コストをヒントとして設定し、それを利用しながら無駄な探索を省くようにする方法。	各地点からゴールまでのヒントがわからない場合には使用できない。

2次元配列

• ９×９のようなマスがあった場合、８１要素の一次元配列とするのではなく、長さ９の１次元配列を９個用意して、３つずつ（１列目・２列目・３列目）で実装できることを２次元配列という。

a = [[1,2,3], [4,5,6], [7,8,9]]

for i in range(0, 3):
    for j in range(0, 3):
        print(a[i][j])

隣接行列

• 頂点数×頂点数の２次元配列を隣接行列という。

• 頂点と頂点を結ぶ「辺」があるかを調べることができる。

• 頂点数が多いとメモリ不足になってしまう。

隣接リスト

• この頂点はどこの頂点へ繋がっているのか調べることができる。

• 頂点数の２乗ではなく、辺の数に比例する。

幅探索リスト

• 「まだ訪問していないこと」をチェックするのが大事！！（これがないと永遠に探索してしまうため）pythonではvisitedを使う。

• 始点から各頂点への「最小移動回数」も保存する。

• dequeを使って実装する。始点からの距離dの頂点たちが取り出されながら、距離d＋1の頂点たちがキューの末尾に入っていき、そして距離dの頂点たちが全て出た後で距離d＋1の頂点たちが取り出されるようになり、距離d＋2の頂点たちがキューの末尾に入る（やっとエンキューからデキューまでのイメージがついた）

• ２次元グリット上で、４近傍を列挙するテクニックがある。（この時盤面の外側まで探索しないように注意する）
  マス(i, j)と隣り合うマスは(i+1, j),(i-1, j), (i, j+1), (i ,j-1)。
  

深さ探索リスト

• 一番深いところまで行ったら戻ってくる必要がある。その時に使うのが「再帰」

• 「再帰」とは関数が自分自身を呼び出す仕組みのこと。

動的計画法

• 設計思想の一つで、まずは小さなサイズの部分をとき、その結果を使って大きなサイズの部分を解くという手順を繰り返して回答を導き出すこと。

• 状態をまとめることで、計算量を削減する。

貪欲法

• いくつかの選択を順番に行う問題において、各選択にて「今選べるもので一番いいもの」を繰り返すと、それが結果として全体最適解になるアルゴリズム。

• 良いものを貪欲に選択し続けると全体最適になるという性質が成り立つものでないと使用できない。

• 実装方法として「あえて最良でないものを選ぶ」ことによって、「全ての選び方の合計ポイント」は「貪欲法の選び方の合計以下」であることを証明する。

Ruby　配列や繰り返し処理を理解する

配列

• 配列は異なるデータ型でも格納する事がOKであること

メソッド	内容
delete_at(1)	2番目の要素を削除
10.divmod(3)	商と余を配列で返す

ブロック

• eachメソッドなどで中身を取り出し、それをどう処理するかがブロック（Rubyではfor文を使わずに、配列自身を繰り返させる）

• 要件を問わず共通する処理はメソッドに、要件によって異なる処理はブロックが行う。

• do~endは{ }に置き換えられる

メソッド	内容
a.delete(2)	配列から値が2の要素を削除（要素と完全一致したものを削除）
delete_if	配列から順番に取り出し、条件に当てはまるものを削除（戻り値が真であれば削除）
map	要素を入れる箱を作ってそこに配列をループした処理を詰め込んでいく
select	真の要素だけを集めるメソッド
find	真の最初の要素だけを集めるメソッド
inject	初回のみ`injectを返し、真の最初の要素だけを集めるメソッド

感想

• 今日は朝3時に起きて勉強していた。夜早めに寝て、朝起きた方が集中できる。

• アルゴリズムについて恥ずかしながら”難しいもの”として距離をおいてしまっていたことに気がついた。

• アルゴリズムは、解決したい問題を抽象化しその解法を構造化したもので、概念を学んでいて面白かった。

• よく私は「仕組みで解決したい」と言っているけれどそれならば、身に付けるべきスキルだと感じ、向き合っていた。

• 図鑑を見て、アルゴリズムを身近にした後、実装するコードの方法を書いていたけれど、コンピュータが理解してくれるように一言一言手順を正しく実装しなければ解くことができず難しさを感じた。

• 「知っていること」もすごく大事だと思った。なぜならば、解く上での注意点だったり、メソッドを使うと手間が省ける部分も多いと思ったため。pythonはアルゴリズムを解くためのメソッドがいっぱいあるんだなと感じた。

• 何が正解かわからないけれど、今自分にできることを全力で行って後悔しないようにする。