アルゴリズムとデータ構造

AIZU ONLINE JUDGEのALDS_1_D　を解いていて、正解に至るまで幾つかの不正解コードを書いてしまいました。この不正解コードの何がダメなのかについて考察していきます。

与えられた図形が凸多角形かどうかを判定するためのアルゴリズムについて紹介します。判定のアルゴリズムには外積を利用しています。

本記事では、最大フローとは何か最大フローを求めるアルゴリズム簡単なグラフを例に、どのようにアルゴリズムが進んでいくかのデモの3点がわかるように解説していきます。最大フロー(最大流)とは何かまずはフローの意味から解説します。フロー(flow)...

転倒数とは昇順になっていない数字の組みの個数を意味します。この転倒数の2種類の解法(バブルソート、BIT)についてまとめました。また、BITのアルゴリズムの挙動を視覚的・数式的な解釈についても詳しくまとめました。

Binary Indxed Tree(BIT)は値の追加・区間和を高速に計算できるデータ構造です。BITをpythonで実装し、アルゴリズムの挙動を一つ一つ詳しく見ていきます。

最小全域木を求めるアルゴリズムの一つがクラスカル法です。本記事ではこのアルゴリズムをpythonで実装します。また、単純なグラフを用いて、どういう流れで最小全域木が導かれるのかを詳しく見ていきます。

ワーシャルフロイド法はグラフの最短経路を求めるアルゴリズムです。本記事ではこのアルゴリズムをpythonで実装し、簡単なグラフを用いてアルゴリズムの挙動を見ていきたいと思います。

トポロジカルソートはグラフの有向辺をすべて左から右方向へ向くように並べ替えるアルゴリズムです。本記事ではこのアルゴリズムをpythonで実装し、さらに閉路検出に応用する方法についても触れたいと思います。

ランレングス圧縮の具体例を導入し、2通りの実装方法についてまとめました。また、具体的な応用例として、AtCoderの問題をランレングス圧縮を用いて解いたコードについても紹介しています。

ベルマンフォード法は最短経路問題をとくためのアルゴリズムの一つです。本記事ではこのアルゴリズムをpythonで実装し、簡単なグラフに適用した際のアルゴリズムの流れを確認していきます。