転倒数を求める問題を解きました。バブルソートの交換回数を数えることによっても求めることができますが、より高速なマージソート を用いた解法を実装します。 問題 次の問題を解きます。 反転数 | アルゴリズムとデータ構造 | Aizu Online Judge 考え方 マ…

データ構造の一つであるDisjoint Setsと、それを管理するUnion-Findアルゴリズムについて勉強した内容のまとめです。 この記事の内容 Disjoint Sets とは何か Disjoint Sets の実装のアイディア 例題を解く Disjoint Sets とは？ 複数の集合を考えたとき、そ…

最短経路問題をやります。最短経路を求めるアルゴリズムとして、ダイクストラ法を取り上げます。最後に問題を解きます。 最短経路問題 重み付きグラフが与えられているとします。最短経路問題とは、ある２点間をつなぐパスを構成する辺の重みの総和が最小と…

最小全域木の基本と、それに関連する知識を簡単にまとめておきます。最後に最小全域木に関する問題を解きます。 最小全域木 全域木 グラフGがあるとします。そして、その部分グラフG'を考えます。G' が G の全ての頂点を含み、かつ辺をできるだけ多く含む木…

連結グラフと連結成分について簡単にまとめてから、問題を解いていきます。 連結グラフ グラフに含まれる全ての頂点が他のいずれかの頂点とリンクしているようなグラフを連結グラフと言います。こんな感じ。 連結成分 あるグラフの部分グラフのうち、極大で…

幅優先探索の勉強メモです。アルゴリズムの解説と、問題を解くことまでをやっていきたいと思います。 幅優先探索 幅優先探索（Breadth First Search, BFS）はグラフを用いた基本的な探索アルゴリズム。近いものから順にアクセスしていく感じ。例えば次のよう…

深さ優先探索を勉強したのでメモしておきます。 深さ優先探索 深さ優先探索（Depth First Search, DFS）はグラフを用いた代表的な探索アルゴリズムです。大まかにスタックを使ったものと再帰を利用したものという２つの実装方法があります。基本的なアイディ…

グラフの基本的な内容です。グラフが隣接リストの形で与えられたとき、隣接行列に直します。 隣接リストと隣接行列 隣接リスト 配列Aを用意します。頂点uに対して、A[u]はuと隣接する全ての頂点を格納します。 隣接行列 ２次元配列Aを用意します。頂点iから…

動的計画法の例題です。連鎖行列積をやります。アルゴリズムの勉強と実装をします。 連鎖行列積 厳しい名前がついていますが、やることは行列の積の計算順序の決定です。 与えられたn個の行列の連鎖の積を計算しますが、計算結果には興味がありません。見つ…

動的計画法の例題です。最長共通部分列を実装します。 目標 最長共通部分列を実装する 最長共通部分列 ２つの列X、Yがあるとします。XとYの共通部分列のうち、最長のものを最長共通部分列（Longest Common Subsequence, LCS）と言います。列は数列など色々な…

動的計画法の例題としておなじみのフィボナッチ数列を実装します。 目標 動的計画法の基本的なアイディアを理解する。 フィボナッチ数列 次のように定義されます。 いかにも再帰関数で書けそうです。 素朴な再帰関数による実装 nを入力として与えると、フィ…

優先度付きキューをヒープを使って実装します。標準ライブラリに入っていますが、勉強するために自分でやってみました。 最後に標準ライブラリの優先度付きキューの使い方も見てみます。 目標 実装を通して優先度付きキューを理解する。 標準ライブラリを使…

今回の主題は二分ヒープです。ヒープはデータ構造の一種。メモリのヒープ領域とは異なります。 完全二分木 上の図のような二分木を完全二分木と言います。全ての葉の深さが同じで、全ての内部ノードが２つの子を持たなければなりません。このように、葉の一…

二分探索木とは何かを簡単に説明してから、実装します。この記事では二分探索木に対する基本的な操作である要素の挿入・探索・削除ができるようになることを目標としています。 二分探索木とは？ 探索木というデータ構造があります。各ノードがキーと値を持…

木の復元の問題です。木の巡回の応用問題となってます。木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge 例 まず、例を見て解き方を考察します。 先行順巡回で P = {1, 2, 3, 4, 5}、中間順巡回で I = {3, 2, 4, 1, 5} という順でノードが訪問され…

木構造を持つデータを探索するアルゴリズムに、木の巡回と呼ばれるものがあります。今回は３種類の木の巡回を取り上げ、それらを実装してみます。 木の巡回 木の巡回とは、ある木に属する全てのノードを順番に１回づつ訪問するアルゴリズムのことを指します…

もっとも高速なソートであると言われているクイックソートを実装します。前回実装したパーティションを利用します。最後に問題を解きます。 パーティションの記事はここ↓ programgenjin.hatenablog.com 目標 クイックソートを実装できるようになる。 クイッ…

高速ソートアルゴリズムに関して、今回はパーティションを実装します。パーティションはクイックソートで利用されています。 流れとしては、パーティションの説明と実装の後、最後に問題を１題解いてみます。 目標 パーティションを実装できるようになる パ…

今まで初等的なソートアルゴリズムである挿入ソート、バブルソート、選択ソートを実装してきました。 しかし、これらは簡単に実装できるものの、遅いです。そこで、今度はより高速なソートアルゴリズムを実装してみたいと思います。今回はマージソートです。…

探索アルゴリズム第2弾、前回の線形探索に引き続き、今回は二分探索についてまとめました。 * 目標二分探索を実装できるようになる。 二分探索 二分探索は、整列された配列に適用できる高速な探索方法です。あらかじめ整列されている必要があることに注意が…

アルゴリズムとデータ構造について勉強していて、探索アルゴリズムについて学んだのでメモを残しておきます。今回は線形探索です。 実装しながら簡単な説明をして、それから問題を解きます。 目標 線形探索を実装できるようになる。 線形探索 多数の要素が並…

データ構造第3弾、今回は連結リストを実装してみます。 これまでスタックやキューを実装してきましたが、今回はちょっとそれらより難しそうです。 目標 標準ライブラリに入っている連結リストを、自分で実装してみることで理解する。 双方向連結リスト 双方…

C++でデータ構造を実装してみるシリーズ。今回はキューを勉強しました。 標準ライブラリにありますが、勉強のために自分で実装します。 目標 キューを自分の手で実装してみる。 キュー キューは先入れ先出し（FIFO: First In First Out）を特徴とするデータ…

プロコンのための勉強の一環としてデータ構造を学習しています。今回はスタックです。 C++の標準ライブラリに入っていますが、勉強のために自分で実装してみます。 目標 スタックを実装する。 スタックとは 後入れ先出し（LIFO: Last In First Out）を特徴と…

初等的ソートアルゴリズム第4弾。今回はシェルソートを実装してみます。挿入ソートの応用です。 挿入ソートがわからない方はこちら↓ programgenjin.hatenablog.com 目標 シェルソートを理解する。例によって問題を解きます。 シェルソート あらかじめある程…

初等的ソートアルゴリズム第3弾。今回は選択ソートです。 目標 選択ソートを理解することを目指します。例によって問題を解くことで理解を深めます。 選択ソート 計算量は。前方のソートずみ部分に、未ソート部分から小さい順に要素を選択して加えていくこと…

木というデータ構造があります。プロコンやグラフ理論の勉強をしていると出てくると思います。木ってなに？という方や、だいたいどんなものかは知っているけど実装したことはないという方に向けて、まず基本的なところをざっくり説明して、それから問題を解…

初等的ソートアルゴリズム第2弾。 今回はやたらと耳にすることが多いバブルソートです。 目標 バブルソートを理解する。実際に問題を解いてみます。 バブルソート 数列を昇順にソートします。計算量はです。 アルゴリズム 昇順になっていない隣接要素がなく…

最近プロコンのためにアルゴリズムの勉強始めたので、メモを残しておきます。まずは基本であるソートをやっていこうかと。今回は挿入ソートです。 目標 挿入ソートを理解する。プロコンの問題を解くことで実装も行う。 挿入ソート 挿入ソートは初等的なソー…