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

AOJ

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_6_A Counting sortを解く話

AOJ

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

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 二重ループの外側と内側の進む向きが違うので注意. 計算量 内側のループのた…