概要 pythonコード 概要 以前この記事で hirohirohirohiros.hatenablog.com エラトステネスの篩は実装しました．しかし，以前のコンテストでこの関数では対応出来ない問題に当たりました． このエラトステネスのふるい関数はiが素数の時リストi番目がTrue，…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの内容 pythonコード 概要 トポロジカルソートは，有向無閉路グラフ(DAG)の各ノードについて，どのノードも出力先のノードより後ろに並ぶように並べるソートです．ようするに，ノードと一列に並べて，辺…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの概要 素因数分解 エラトステネスの篩 pythonコード 素因数分解 エラトステネスの篩 概要 整数を引数にとり素因数分解し，keyを素因数，valueを指数としたdictを返す関数を作ります．素因数分解には試し…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの概要 併合，判定 rank pythonコード 概要 Union Findはグループ分けを管理するデータ構造です．要素aと要素bが同じグループに属しているかそうでないか判別することが出来ます． また，複数のグループ…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの内容 pythonコード 概要 ベルマンフォード法はダイクストラ法と同じ最短路を求めるアルゴリズムです．ダイクストラ法と違い，負辺が存在しても正しく動きます．また，負の閉路を検出することも出来ます…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの内容 pythonコード 概要 ダイクストラ法はグラフの最短路を求めるアルゴリズムです．グラフの2頂点が与えられたとき，その2頂点を始点終点としたときのルートで最もコストが小さいものを最短路と言いま…

概要 一覧 ダイクストラ法 ベルマンフォード法 Union Find 素因数分解，エラトステネスの篩 トポロジカルソート docstring 概要 名前の付いたアルゴリズムについて，毎回その場で調べて実装を繰り返していましたが，さすがに面倒くさい，時間が掛かって不利…