アルゴリズム

[C#] ベルマンフォード法で単一始点最短経路問題を解くための実装方法

ベルマンフォード法とは ベルマン–フォード法 – Wikipedia ベルマンフォード法はダイクストラ法と同じく、単一始点の最短経路問題を解くためのアルゴリズムの一種です。開始点からすべての点への最短経路を求めることができます。 ダイクストラ法との違いは以下の2点です。 計算量はダイクストラ法よりもベルマンフォード法のほうが大きい。 ベルマンフォード法は負の重みを扱える。 ベルマンフォ […]

[C#] 最小公倍数(LCM)を求めるアルゴリズムと実装

最小公倍数 – Least Common Multiple 最小公倍数 – Wikipedia 最小公倍数とは、0ではない複数の整数の公倍数のうち最小の自然数をさします。 最小公倍数の求めかた 2つの正整数(a, b)の最小公倍数は、最大公約数が求めれば簡単に求まります。なぜなら最大公約数と最小公倍数には以下のような性質があるためです。 a * b = Gcd(a, b) […]

[C#] ユークリッドの互除法で最大公約数を求める方法

最大公約数を求めるプログラム 2つの自然数の最大公約数を求めるアルゴリズムの1つに、ユーグリッドの互除法 があります。これをプログラムで実装する方法をまとめます。 ユークリッドの互除法とは ユークリッドの互除法 – Wikipedia 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に […]

[C#] Union-Find木を実装する方法

Union-Find木 とは 素集合データ構造は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。 Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。 Union: 2つの集合を1つに統合する。 これら2つの操作をサポ […]

[C#] lower_bound, upper_bound を実装する方法(二分探索)

lower_bound と upper_bound lower_bound と upper_bound という2つの関数があります。これは C++ のSTLライブラリにある関数です。この関数を C# で実装していきます。 lower_bound – cpprefjp C++日本語リファレンス upper_bound – cpprefjp C++日本語リファレンス これらの関 […]

[C#][DP] A – コンテスト(Typical DP Contest) を解く [動的計画法]

C# で動的計画法(DP)を解きたい 最近競技プログラミングをやりだして、動的計画法(DP)というアルゴリズムを知りました。練習でいろいろな問題を解いていこうと思います。そして勉強がてら解けた問題の内容を書いていきます。 Typical DP Contest – Typical DP Contest | AtCoder DPの問題に特化した過去のコンテストがあるのでこれを順に C# で […]

[C#] フィボナッチ数を動的計画法とメモ化で求める [VB]

動的計画法(Dynamic Programming)とは 動的計画法 – Wikipedia 動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 簡単に言うと、一度計算した結果を保持 […]

[C#][VB] 二分探索(バイナリサーチ)の実装

二分探索(バイナリサーチ)とは 二分探索 – Wikipedia 二分探索(にぶんたんさく、英: binary search、BS)やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。 要素数nの配列に対して線形探索する場合(先頭から順番に探す方法)は、時間計算量が O(n) となります。それに対して二分探索(バイナリサーチ)は O(log n) と高速に動作します。た […]

[C#][VB] 優先度付きキューを実装する方法

優先度付きキュー(PriorityQueue) 優先度付きキュー(Priority Queue)は、優先度に従って優先的に要素を取り出せるコレクションです。 単純なキューだと先入れ先出し(FIFO)ですが、取り出すときに優先度の高い要素(例えば値の大きいもの)から順番に取り出せるというキューになります。例えば普通のキューだと 3, 5, 1 の順に入れるとその順番に取り出せますが、これを優先度に従 […]