四十三庵

蔀の雑記帳

資格・勉強

資格関係の勉強ノート

アルゴリズム設計法

目次 目次 brute force solution Dynamic Programming Solution(動的計画法) 分類 Divide and conquer solution (分割統治法) Greedy Method(欲張り法) brute force solution 日本語の訳語がない セキュリティの文脈ではよくブルートフォースアタック…

Boyer-Moore String Search

理想的な場合はO(N/M)で探索できる 検索対象のワードの右から順に探索することで、スキップ量を大きくする

Knuth-Morris-Pratt String Search

単純な文字列検索は検索対象の文章の長さNと検索ワードの長さMのO(MN)になる KMPアルゴリズムを使うとO(N)でいける ただし検索ワードのスキップ量があらかじめ設定されている場合 発想としては、検索対象の文字を一文字ずつ照合していくと、 実は明らかにス…

Kruskal's Algorithm

実装 func minimumSpanningTreeKruskal<T>(graph: Graph<T>) -> (cost: Int, tree: Graph<T>) { var cost: Int = 0 var tree = Graph<T>() let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < $1.weight }) var unionFind = UnionFind<T>() for vertex </t></t></t></t></t>…

Prim’s Algorithm

計算量はO(n2) 解説はここがわかりやすかった 実装 func minimumSpanningTreePrim<T>(graph: Graph<T>) -> (cost: Int, tree: Graph<T>) { var cost: Int = 0 var tree = Graph<T>() guard let start = graph.vertices.first else { return (cost: cost, tree: tree) } v</t></t></t></t>…

Minimum Spanning Tree

重み付けのあるグラフに対して、コストが最小となるスパニングツリーを求めるアルゴリズム。 Prim’s Algorithm / Kruskal's Algorithmが二大解法

BFSとDFS

Breadth-First Search: 幅優先探索 Depth-First Search: 深さ優先探索 BFSは開始するNodeをキューに入れ、一度デキューしてから、隣接するNodeをキューイングする。 そしてDequeueしたNodeの隣接しているNodeをenqueueする…… (一度enqueueしたNodeはもうenq…

Dijkstra Algorithm

有向グラフの最短経路を見つけるためのアルゴリズム 計算コストはO(N2) 経路コストの計算にヒープを使うと、約O(2NlogN)までパフォーマンスが改善する 節点と辺の数が同程度の時に限るらしい 辺が多くなる(例えば全ての節点がつながれた完全グラフの時)は…

Warshall–Floyd Algorithm

ダイクストラと発想は同じだが、出発点が存在せず、全ての節点と全ての接点のコストテーブルを更新する コストテーブルのサイズはN*N 計算量はO(N3) 計算量はダイクストラよりN回倍多いが、実装が楽で、接点を結ぶ辺が多い際は有効 実装 import Foundation l…

グラフ理論

前提 本を読んだだけだと、グラフ理論そのものがよくわらかなかったので、前提を調べた。 内容 最終的なアウトプットが表になるかTreeになるかでわかれる グラフ理論では頂点のことをVertex、辺のことをEdgeと呼ぶ慣習があるよう。 Vertex = Node, Edge = li…

Bucket Sort

要素のとりうる値の範囲(バケット)に応じて挿入して、最後にmapするようなSort方法 特定の条件では計算効率がよい場合がある バケットがm個のとき、m < NならO(N)になる。

Heap Sort(ヒープソート)

Heapを使ってSortする Performance of heap sort is O(n log n) in best, worst, and average case 実装 Heapの実装にどっかバグがあって、上手くソートできなかった。 一日格闘してダメだったので、SACの模範解答見てお茶を濁した。 import Foundation stru…

Merge Sort(マージソート)

最悪計算量でもO(NlogN) メモリ領域はO(N)分食う フォンノイマンが考えたアルゴリズムらしいが、考え方はシンプルだし、計算効率いいし実用的 配列の真ん中から要素を分けて、それを繰り替えして、要素二つにしたらmerge() mergeされた配列は再帰的にどんど…

Quick Sort(クイックソート)

配列の最初の要素と二番目の要素の大きい方をpivotとして、その値との大小関係を使ってSortする 計算量は平均でO(NlogN) 最悪の場合はO(N2) 本の通り実装しようとしたら、Arrayはstructなので再帰ができなくて、 しかも引数のArrayはimmutabelで直接操作でき…

Bubble Sort(バブルソート)

小さな泡が水から浮き上がるようにソートすることから 「配列の最後からその一個前の要素を大小比較して、逆だったら要素を入れ替える」という操作を最初の要素の一個前まで行うことで最小の要素が配列の最初になる その操作を次は最初の要素の二個前まで行…

Hash

ハッシュ値を使うとO(1)で値を求められる 衝突という問題がある 衝突を回避するためには二つ方法がある チェイン法(chaining mechanism) 衝突した値はリスト構造でenqueして格納する 開番地法(open addressing) 衝突したら再ハッシュを行い、空いている…

B Tree(B木)

ノート balanced treeの例 A B-Tree of order n satisfies the following properties: Every node has at most 2n keys. Every node (except root) has at least n keys. Every non-leaf node with k keys has k+1 children. The keys in all nodes are sort…

AVL Tree

ノート ソビエト連邦時代のロシア人が論文書いたデータ構造。 平衡木の例 回転処理で計算量の効率性を保つ 実装例までは追えず

2-3 Tree(2-3木)

ノート balanced tree(平衡木)の例として2-3木が紹介されている 二分探索木はあくまで平均の計算量がO(logN)となるだけで、操作の結果によっては最悪の計算量O(N)になりうる そこでbalanced treeは常に計算量がO(logN)となるように要素を挿入・削除するた…

Binary Search Tree(二分探索木)

BSTとは 任意の要素の取得がO(logN)で済む構造 計算量がO(logN)ですむ証明が難しかった 実装 最初Structでやろうとしたら、再帰にできなくて死んだ ただ再帰でやることを思いついてしまうと、実装時間としてはそんなにかかんなかった if文2回ネスト(2×2)す…

Heap

基本教科書を読んでわかることは書かなくて、読んでいてわからなかった点や、 実際に手動かして書いてみたコードなんかを書いています。 Heapとは www.raywenderlich.com ここの説明がわかりやすい。 英語の意味 英語のHeapの意味は積み重ね heap of moneyな…

なぜデータ構造とアルゴリズムを学ぶか

2020/2〜3月にデータ構造とアルゴリズムを勉強したので、その勉強ノートをブログで公開して行こうと思う。 下記の本を使いました。 目次 目次 方法と期間 目的 技術力とは? フレームワークがあれば不要だよ論 次回予告 方法と期間 五十嵐健夫さんの…

データ構造とアルゴリズムノート 目次

2020/2〜3月にデータ構造とアルゴリズムを勉強したので、その勉強ノートをブログで公開する。 全体 はじめに データ構造とアルゴリズムノート 目次 なぜデータ構造とアルゴリズムを学ぶか データ構造 Heap Binary Search Tree(二分探索木) 2-3 Tree…

ノート:情報セキュリティスペシャリスト

情報セキュリティスペシャリストを受けた時にEverNoteで作ったノート。 公開する価値がどこまであるかはわからないけども、何かの参考になれば。対策方針 ・クロスサイトスクリプティング ・暗号化技術の技術 ・ハッシュ ・メールセキュリティ ・ファイアウ…

原価厨につける薬(原価計算)

「外食する奴はアホ。原価考えろ」とはよく言われることで、 2ちゃんねるなんかでは、そのあまりのウザさから「原価厨」という素敵な名前をつけられている。 原価数十円のカレーを外食する奴はアホ。見てるだけでイライラする14 : 名無しさん@涙目です。(…

なぜ僕は独学で効率よく簿記三&二級に合格できなかったのか

・独学で効率よく簿記三&二級に合格するための僕の方法(ミームの死骸) ・簿記2,3級を独学で同時に3週間で受かる方法(はてな匿名ダイアリー)僕も一応簿記二級・三級は持ってるし、 「よーし僕もこの手のハウツー記事書いてはてブ乞食すっぞ!」 と思った…

ノート;ミクロ経済学4(家計;所得効果と代替効果)

ノート;ミクロ経済学1(ミクロ経済学の設定) ノート;ミクロ経済学2(家計の効用最大化問題1) ノート;ミクロ経済学3(家計の効用最大化問題2) の続きです。労多くして実り少ない記事なので、あんまりモチベーション上がらないんですが、 たま〜に…

憲法ノート

1.憲法の改正の「限界」と日本国憲法制定の際の諸問題を述べよ シェイエスは「憲法につくられた力」と「憲法をつくる力」に二分し、カール・シュミットは憲法律と憲法の基本原則に二分した。憲法改正において改正できるのは前者の「憲法につくられた力」や「…

金銀ノート

そろそろコモディティ投資を真面目に勉強すべきなのではないかという訳で、金と銀について調べている。 原油にも大いに興味がある。 (天然ガスに投資できれば一番いいんだろうけど、投資手段を知らない) (追記;天然ガス連動ETFはある模様) 今回はとりあ…

地理学ノート

地理学について(雑感) 地理学ほどつかみどころのない学問もないだろう。 社会科の教員免許をとるためには、地理学・地誌学の講義を受けることは、 大抵の大学で必須となるはずだが、僕なんかは血の涙を流しながら受けている。 教職・歴史科目はまだしも、…