「ネタ」の記事一覧

ひとりで勝手にはじめた蟻本読書会 グラフ理論 いわゆる牛ゲーと最短路問題とベルマンフォード法 蟻本読書会 の続きです。 ワーシャルフロイド法と全ペアの最短経路 ワーシャルフロイド法は、重み付き有向グラフの全ペアの最短経路・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 最小全域木問題 クラスカル法 蟻本読書会の続きです。 ベルマンフォード法とは？ ベルマンフォード法は、重み付き有向グラフにおける単一始点の最短経路問題を解くアルゴリズムのひと・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 最短路問題 ダイクストラ法 蟻本読書会の続きです。 最小全域木問題とクラスカル法 最小全域木とは、グラフが連結であるという条件を保ったまま辺を消去して得られる木のなかで辺のコ・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 二部グラフ判定 蟻本読書会の続きです。 ダイクストラ法と最短路問題 ダイクストラ法（だいくすとらほう、英: Dijkstra’s algorithm）はグラフ理論・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 データ構造 Union-Find 木 蟻本読書会の続きです。 グラフと二部グラフ グラフとは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成されるデータ構造です。 鉄道や・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 データ構造 set, map 編 蟻本読書会の続きです。 Union-Find木とはグループ分けを木構造で管理するデータ構造です。このデータ構造であれば、同じグループに属するなら同じ木に・・・

続きを読む

c++ には set と map があります。setは重複を許さない順序付き集合です。重複データがある場合は、重複データは自動的に削除されます。またmapは各要素がキーと値を持ち、同じキーが重複することがありません。 C・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 動的計画法 01ナップサック問題 蟻本読書会の続きです。 最長共通部分列問題 最長共通部分列 ある列 Z が X と Y 両方の部分列であるとき、Z を X とY の共通部分列と言います・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 本当は難しい貪欲法 選択肢を多く残す 蟻本読書会の続きです。今回から動的計画法ゾーンに入ります。 01ナップサック問題とは？ ナップサック問題、価値 viと重量 wi をもつ n 種類の・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 猪突猛進！ 貪欲法 区間スケジューリング問題 辞書順最小など 蟻本読書会の続きです。 貪欲法とは「問題を部分問題に分割して，各部分問題に対する局所最適解を求めることを繰り返すという手法」・・・

続きを読む