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

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

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

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

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

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

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

クイックソートで使う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．（実…