2020年1月20日動的計画法入門,動的計画法,DP,競プロ,ナップサック

動的計画法とは

動的計画法(Dynamic Programming)とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。

以下のような特徴がありますが、抽象的なのでここではざっと眺 ...

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

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

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

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

大まか ...

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

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

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

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

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

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

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

グラフとは

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

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

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

2019年11月25日データ構造入門,データ構造,連結リスト

連結リストとは

連結リストはノードと呼ばれるデータの塊が、複数繋がってできたデータ構造です。

1つのノードは、格納する値自体と、次のノードへのアドレスを保持します。先頭から各ノードを辿ることで、線形に連結リストを探索すること ...

2019年11月25日データ構造入門,データ構造

データ構造とは

データ構造とは、「コンピューターがデータを効率的に扱うための方法や構造のこと」です。これには様々な種類があり、それぞれに特徴があります。

アルゴリズムの話をする際に必ずと言っても良いほど出てくるのがデータ構造 ...

2019年11月25日データ構造入門,データ構造,配列

配列とは

配列は、連続したメモリ領域にデータを格納するシンプルなデータ構造です。データにアクセスしたい時は、配列の先頭から見て何番目のデータを取り出したいか(index)を指定します。

プログラミングを学ぶときに、必ずと学ぶ ...

2019年11月25日データ構造入門,データ構造,map

辞書はどのようなデータ構造か

「辞書」は「連想配列」・「ハッシュ」・「マップ」とも呼ばれるデータ構造の1つです。

鍵(key)の集合で構成されており、それぞれのkeyは1つの値と結びついています。keyを指定することで、それ ...

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

ソートとは

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

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