2020年1月19日貪欲法入門,競プロ,貪欲法

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。

その場での最善の手を選ぶことを繰り返す

貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。

大まか ...

2019年12月6日数学競プロ,ユークリッドの互除法,拡張ユークリッドの互除法,最大公約数

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られ ...

2019年12月4日数学剰余,二項係数,テーマ記事,競プロ,素数,逆元

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。

...

2019年12月2日探索順列

\(n!\) 通りの全探索を行いたい時に順列が用いられます。

順列(permutation)とは、n 個のものを順番に並べるのは何通りあるかを考える問題です。n 個全てを区別できるなら、\(n!\) 通りの並べ方があります ...

2019年11月30日探索入門,幅優先探索,グラフ,キュー

幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。

木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...

2019年11月30日探索入門,幅優先探索,スタック,再帰関数,全探索

深さ優先探索とは、全探索アルゴリズムの一種です。グラフや、グラフと同一視できるものを探索する際に良く使われます。

幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を ...

2019年11月30日グラフ入門,グラフ,有向グラフ,データ構造,無向グラフ,重み付きグラフ,用語・定義

グラフとは

頂点(ノード)と、頂点同士の関係を表したデータ構造です。

数学的には、グラフは以下の2つから構成されます。

頂点(ノード)の集合
頂点同士がつながっているか(隣接しているか)を表す、辺(エッジ)の集合 ...

2019年11月25日ソートソート,入門

ソートとは

ソート(整列)とは、配列などのデータ構造について、ある順序関係に沿うように順番を入れ替えることです。簡単に言えば、小さいものから大きいものへと並ぶように整列させるようなものです。

ソートを行う場面は非常に多いため ...

2019年11月24日ソート入門,ソート,クイックソート

クイックソートとは

クイックソートは分割統治法を用いたソートアルゴリズムの一種です。安定ではない内部ソートとなっています。マージソートの様に、再帰関数を用いることで配列を2分割してソートします。

マージソートは分割した配列を ...

2019年11月24日ソート入門,ソート,マージソート,分割統治法

マージソートとは

マージソートは分割統治法を用いたソートアルゴリズムの1つです。配列を2分割することを繰り返し、小さい配列を一つ一つソートしてから「マージ(併合)」することで、最終的に高速にソートができます。

最終的に1つの ...