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

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

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

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

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

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

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