貪欲なアルゴリズム（greedy）入門
貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。
その場での最善の手を選ぶことを繰り返す貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。
大まか ...
ユークリッドの互除法
2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。
このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られ ...
競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ
競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。
...
順列(n!)の全探索
\(n!\) 通りの全探索を行いたい時に順列が用いられます。
順列(permutation)とは、n 個のものを順番に並べるのは何通りあるかを考える問題です。n 個全てを区別できるなら、\(n!\) 通りの並べ方があります ...
幅優先探索(Breadth First Search)の基本
幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。
木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...
深さ優先探索(Depth First Search)の基本
深さ優先探索とは、全探索アルゴリズムの一種です。グラフや、グラフと同一視できるものを探索する際に良く使われます。
幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を ...
グラフ(Graph)のデータ構造と基本用語の定義
頂点(ノード)と、頂点同士の関係を表したデータ構造です。
数学的には、グラフは以下の２つから構成されます。
頂点（ノード）の集合頂点同士がつながっているか(隣接しているか)を表す、辺（エッジ）の集合 ...
ソートアルゴリズムの概要
ソート（整列）とは、配列などのデータ構造について、ある順序関係に沿うように順番を入れ替えることです。簡単に言えば、小さいものから大きいものへと並ぶように整列させるようなものです。
ソートを行う場面は非常に多いため ...
クイックソート(QuickSort)
クイックソートは分割統治法を用いたソートアルゴリズムの一種です。安定ではない内部ソートとなっています。マージソートの様に、再帰関数を用いることで配列を2分割してソートします。
マージソートは分割した配列を ...
マージソート(Merge Sort)
マージソートは分割統治法を用いたソートアルゴリズムの1つです。配列を2分割することを繰り返し、小さい配列を一つ一つソートしてから「マージ(併合)」することで、最終的に高速にソートができます。
最終的に1つの ...