きままにものづくり

日々の気付いたことなんかを書いてます。

アルゴリズム

最長共通部分列

コード 実装日 一回目:1/4 テスト 関連問題

巡回セールスマン問題(ループ)

コード 実装日 一回目:1/3 テスト 関連問題

重複組合せ

コード 実装日 一回目:1/3 テスト 関連問題

バブルソート

コード 実装日 1回目:11/15 テスト ALDS LESSON 2 A 関連問題 ALDS LESSON 2 A

最長部分増加列 O(n log n)

コード 実装日 1回目:11/11 テスト POJ1631 関連問題 POJ1631

アルゴリズム

一般的なアルゴリズムのC++実装の一覧を示す。アルゴリズムは実装しないとすぐに忘れてしまうので、一日ひとつのアルゴリズムを実装する。繰り返し実装することで定着させる。 動的計画法 ナップサック問題 01ナップザック問題 O(N W) O(N V) 個数制限なしナ…

グラフ理論-アルゴリズム-

グラフ理論に関するアルゴリズムを紹介する。 最短経路問題 ベルマン-フォード ダイクストラ ワーシャル-フロイド 最大フロー問題 フォード-ファルカーソン

数論-アルゴリズム-

主に初頭整数論におけるアルゴリズムを説明する。 テクニック MOD乗算 MOD指数演算 理論 ユークリッドの互除法 拡張ユークリッドの互除法 ポラード・ロー素因数分解 モジュラ逆数 中国余剰定理 素数判定 エラトステネスのふるい フェルマーテスト ミラーラビ…

フォード-ファルカーソン

フォード-ファルカーソン法は、最小フロー問題を解くアルゴリズムのひとつである。 目次 アルゴリズムの説明 計算量 コード アルゴリズムの説明 このアルゴリズムを説明する前に、残余ネットワークの説明をする。残余ネットワークとは、現状での流すことがで…