読者です 読者をやめる 読者になる 読者になる

ALDS_11_A Graphを解く話

AOJ

グラフの表現の理解を問う問題である. 隣接リスト表現から隣接行列表現へ変換する処理を実装する. 隣接リスト表現(Adjacency List) ・有限グラフを表現するためのリスト・1つのリストが1つの頂点に対応して,隣接するノードが接続 隣接行列表現(Adjacenc…

ALDS1_8-A Binary Search Tree Iを解く話

AOJ

根付き木,二分木に続いて二分探索木を実装する. 二分探索木(Binary Search Tree) ・内部接点はが {キー,左部部分木, 右部分木} を持つような根付き木. ・二分探索木条件(Binary search tree property)を満たす木. 二分探索木条件: 左部分木の根 <= キ…

ALDS1_7_B Binary Treeを解く話

AOJ

二分木を実装させる問題である. tooshitaka.hatenablog.com とほとんど同じだ. まず用語の整理からする. 二分木 ・ノードの子の数が最大でも2である木. ・子は左,右と区別される. ノードの高さ ・木の最下段からへのパスを考えたとき,通る辺の数. ノ…

ALDS1_7_A Rooted Treesを解く話

入力を根付き木として保存する問題である. ノードの深さ,種類(根,内部ノード,葉),深さも答えさせるのでそれぞれの概念の定義をきちんと理解する必要がある. 木(Tree) ・連結で閉路をもたないグラフ. ・木について話すときは頂点(Vertex)をノー…

ALDS1_2 Bubble sortを解く話

そらで書けないと恥ずかしいバブルソートを実装する. 特徴 ・「泡がぶくぶく...」という説明で有名 ・ 配列の要素数が大きい場合は計算量が大きくなるので非実用的 アルゴリズム Bubblesort(A) n = A.length for i = 0 to n - 1 for j = n - 1 downto 1 …

ALDS1_6_A Counting sortを解く話

AOJ

計数ソート(Counting sort)を実装する. 特徴 配列の要素をキーとするソートアルゴリズム キーを要素とする別の配列を用意して出現頻度と累積和を計算 累積和から任意のキー以下の要素数がわかり,正しい位置に要素を代入 アルゴリズム A: ソートする配列…

ALDS1_6 Quick Sortを解く話

情報系の学生ならみんな知っているクイックソートを解く. 自分は学部時代にやったはずだが,まったく覚えていなかった. 特徴 配列を分割統治でソートするアルゴリズム 配列を2つに分割する際におおまかにソート(Partitionアルゴリズム) 分割した配列を引…

ALDS1_6-B Partitionを解く話

AOJ

クイックソートで使うPartitionを実装する. 特徴 ・閾値以下か,それより大きかで配列を分割するアルゴリズム. ・閾値で分けるだけなので全体はソートされない. アルゴリズム Partition(A, l, r) threshold = A[r] i = l - 1 for j = l to r - 1 if A[j] …

ALDS1_5_B Merge Sortを解く話

AOJ

AOJのマージソートを実装する問題です. 特徴 ・分割統治と再帰を上手く使ったソーティングアルゴリズム ・配列を1要素になるまで分割してくっつき直すときに比較. アルゴリズム Mergesort(array, left, right) 要素数が1ならソート済みなのでreturn.(実…

ALDS_1_1_A: Insertion Sortを解く話

AOJ

挿入ソートを実装する. 特徴 未ソート部とソート済み部に分けてソート トランプの手札を並べ替える感じ 挿入ソートの改良版がシェルソート アルゴリズム これ. www.youtube.com 二重ループの外側と内側の進む向きが違うので注意. 計算量 内側のループのた…

「国際会議論文の読み方・書き方」を読んだ話

http://www.phontron.com/slides/neubig15nlptutorial.pdf グラムニュービック先生が書いたチュートリアルスライドである. とても良い. 最近は論文を読むときに,このスライド通りに書かれているか自分の頭の中でチェックしている.たまにチェック項目を忘…

「研究者を目指す普通の学生諸君に」を読んだ話

http://hflab.k.u-tokyo.ac.jp/staff/hori/essay/kenkyuu.html を読んだ. 東京大学の堀先生という方のエッセイである. 博士課程の学生or目指している学生に向けた内容だが,修士の学生も読んでピンとくるものがあるだろう. 研究を(まじめに)する学生は…

OpenCVでSlidingWindowする話

物体検出や顔検出とかで必要になるSlidingWindowのメモ 参考 funvision.blogspot.jp 上のサイトを見れば問題なかった. StepSideを小さくするとちょっとずつパッチ切り取るようになる. あとはこのパッチから特徴抽出とかして分類器にぶち込めばいいのかな?…

C++でdlibのSVMを動かした話

巷ではディープラーニングが流行っていますがdlibを使ってサポートベクトルマシーンをやってみる話です. 結論からいうと 凄い使いやすかった. いい感じに抽象化されている. パラメータの調整も何をやっているのか分かりやすい. てな感じ. この記事では…