このサポートページでは、マイナビ出版発行の書籍「アルゴリズムビジュアル大事典」にて作成しましたシンボル、アニメーション、疑似コードを掲載いたします。また、内容のアップデートを行ってまいります。詳しい解説は、本書をご参考にしてください。

アニメーションコントローラの使い方はクイックマニュアルでご確認頂けます。

補足情報が表示されているトピックにつきましては、ご注意ください。その他の訂正等は正誤表をご覧ください。ご質問、不具合等のご報告は、ご遠慮なくy.watanobe@gmail.com(渡部)までお送りください。

Part 1 準備編

3章 計算量

定数倍 定数
対数 対数
線形 線形
線形・対数 線形・対数
二次関数 2次関数
三次関数 3次関数

Part 2 空間構造

4-9章 

シングルノード シングルノード
1次元配列 1次元配列
2次元配列 2次元配列
二分木 二分木
おおよそ完全二分木 おおよそ完全二分木
完全二分木 完全二分木 補足
無向グラフ 無向グラフ
有向グラフ 有向グラフ
森
二次元点群 2次元点群
連結リスト 連結リスト
動的な二分木 動的な二分木

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

10章 入門

2020/05/17
スワップ
スワップ
異なる2つの変数の値を入れ替えてください。
スワップ | 入力 スワップ | 出力
2020/05/17
最大値
マックス
与えられた2つの整数のうち、大きい方を選択してください。
最大値 | 入力 最大値 | 出力
2020/05/17
スワップによるソート
スワップによるソート
3つの整数を小さい順に並べ替えてください。
スワップソート | 入力 スワップソート | 出力

11章 配列に対する基本クエリ

2020/05/17
合計
合計(サム)
与えられたN個の整数の和を求めてください。
合計 | 入力 合計 | 出力
2020/05/17
最小要素の値
最小要素の値
与えられたN個の整数の中で最も小さい「値」を求めてください。
最小要素の値 | 入力 最小要素の値 | 出力
2020/05/17
最小要素の位置
最小要素の位置
与えられたN個の整数の列の要素の中で、最も小さい要素の「位置」を求めてください。
最小要素の位置 | 入力 最小要素の位置 | 出力

12章 探索

2020/05/17
線形探索
線形探索
配列の中から、指定された値を探してください。
線形探索 | 入力 線形探索 | 出力
2020/05/17
二分探索
二分探索
要素が昇順に整列された配列の中から、指定された値を探してください。
二分探索 | 入力 二分探索 | 出力

13章 配列要素の並び替え

2020/05/17
リバース
リバース
整数の列の要素を逆順に並び替えてください。
リバース | 入力 リバース | 出力
2020/05/17
挿入
挿入
昇順に整列された整数の列に、昇順を保つように1つの整数を追加してください。
挿入 | 入力 挿入 | 出力
2020/05/17
マージ
マージ
それぞれ昇順に整列された2つの整数の列を、1つの昇順に整列された整数の列として統合してください。
マージ | 入力 マージ | 出力
2020/05/17
パーティション
パーティション
配列の適当な1つの要素を基準として、基準より小さいグループと大きいグループに分割してください。
パーティション | 入力 パーティション | 出力

14章 遅いソート

2020/05/17
バブルソート
バブルソート
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
バブルソート | 入力 バブルソート | 出力
2020/05/17
選択ソート
選択ソート
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
選択ソート | 入力 選択ソート | 出力
2020/05/17
挿入ソート
挿入ソート
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
挿入ソート | 入力 挿入ソート | 出力
※このアルゴリズムは、本書に含まれません。2020/05/13
シェーカーソート
シェーカーソート
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
シェーカーソート | 入力 シェーカーソート | 出力

15章 整数に関するアルゴリズム

2020/05/17
エラトステネスの篩
エラトステネスの篩 ★★
整数iが素数のときi番目の要素が1、合成数のとき0となるような素数表を作成してください。
エラトステネスの篩 | 入力 エラトステネスの篩 | 出力
2020/05/17
ユークリッドの互除法
ユークリッドの互除法 ★★
2つの整数の最大公約数を求めてください。
ユークリッドの互除法 | 入力 ユークリッドの互除法 | 出力

16章 基本データ構造1

2020/05/17
スタック
スタック
最後に挿入したデータを優先的に取り出すLast-In-First-Out (LIFO)のルールに従ったデータ構造を実装してください。
スタック | 入力
スタック | 出力
2020/05/17
キュー
キュー
最初に挿入したデータを優先的に取り出すFirst-In-First-Out (FIFO)のルールに従ったデータ構造を実装してください。
キュー | 入力
キュー | 出力

17章 配列に対する計算

2020/05/17
累積和
累積和 ★★
整数の列と、それに対するQ個の区間が与えられます。各区間の和を求めてください。
累積和 | 入力 累積和 | 出力
2020/05/17
1次元累積和
1次元累積和 ★★
複数の線分が与えられるので、各座標について重なっている線分の数を求めてください。
1次元累積和 | 入力 1次元累積和 | 出力
2020/05/17
2次元累積和
2次元累積和 ★★★
複数の長方形が与えられるので、各座標において重なっている長方形の個数を求めてください。
2次元累積和 | 入力 2次元累積和 | 出力
※このアルゴリズムは、本書に含まれません。2020/06/07
グリッド上の動的計画法
グリッド上の動的計画法 ★★
格子状の道路網があります。最北西の交差点から最南東の交差点までの最短経路の数を求めてください。工事中の交差点は通れません。
2次元累積和 | 入力 2次元累積和 | 出力

18章 ヒープ

2020/05/17
アップヒープ
アップヒープ
最大ヒープに対して、一つのノードの値が、優先度が増加するように更新されました。最大ヒープを再構築してください。
アップヒープ | 入力 アップヒープ | 出力
2020/05/17
ダウンヒープ
ダウンヒープ
最大ヒープに対して、一つの要素が、優先度が減少するように更新されました。最大ヒープを再構築してください。
ダウンヒープ | 入力 ダウンヒープ | 出力
2020/05/17
ビルドヒープ
ビルドヒープ ★★
適当な整数の列から最大ヒープを構築してください。
ビルドヒープ | 入力 ビルドヒープ | 出力
2020/05/17
優先度付きキュー
優先度付きキュー ★★
優先度が最も高いデータ(ここでは値が大きいもの)を優先的に取り出すルールに従ったデータ構造を実装してください。
優先度付きキュー | 入力
優先度付きキュー | 出力

19章 二分木

2020/05/17
先行順巡回
先行順巡回
二分木のノードを次の条件を満たすように訪問してください:子よりも親を優先的に訪問する。
先行順巡回 | 入力 先行順巡回 | 出力
2020/05/17
後行順巡回
後行順巡回
二分木のノードを次の条件を満たすように訪問してください:親よりも子を優先的に訪問する。
後行順巡回 | 入力 後行順巡回 | 出力
2020/05/17
中間順巡回
中間順巡回
二分木のノードを次の条件を満たすように訪問してください:親が左の子の子孫の後、右の子の子孫の前に訪問される。
中間順巡回 | 入力 中間順巡回 | 出力
2020/05/17
レベル順巡回
レベル順巡回 ★★
二分木のノードを次の条件を満たすように訪問してください:深さがkのノードを訪問する前に、深さがk-1の全てのノードが訪問されている。
レベル順巡回 | 入力 レベル順巡回 | 出力

20章 ソート

2020/05/17
マージソート
マージソート ★★
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
マージソート | 入力 マージソート | 出力
2020/05/17
クイックソート
クイックソート ★★
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
クイックソート | 入力 クイックソート | 出力
2020/05/17
ヒープソート
ヒープソート ★★
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
ヒープソート | 入力 ヒープソート | 出力
2020/05/17
計数ソート
計数ソート ★★
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。ただし、各整数の上限は比較的小さいものとします。
計数ソート | 入力 計数ソート | 出力
2020/05/17
シェルソート
シェルソート ★★
整数の列{a0, a1, ..., aN-1}を小さい順に並べ替えてください。
シェルソート | 入力 シェルソート | 出力

21章 基本データ構造2

2020/05/17
連結リスト
連結リスト ★★
要素の挿入、検索、削除を行うデータ構造を実装してください。
連結リスト | 入力
連結リスト | 出力
2020/05/17
ハッシュ表
ハッシュ表 ★★
データの検索・追加・削除を行う、辞書の機能を提供するデータ構造を実装してください。
辞書 | 入力
辞書 | 出力

22章 幅優先探索

2020/05/17
幅優先探索
幅優先探索 ★★
適当な始点から出発し、グラフの全てのノードを体系的に訪問してください。
幅優先探索 | 入力 幅優先探索 | 出力
2020/05/17
BFSによる最短距離
BFSによる距離の計算 ★★
各ノードについて、始点からの最短距離を求めてください。ここで、距離はエッジをたどる回数とします。
BFSによる最短距離 | 入力 BFSによる最短距離 | 出力
2020/05/17
Kahnのアルゴリズム
Kahn のアルゴリズム ★★
タスクと依存関係を表す有向グラフから、タスクを処理する順番を求めてください。
トポロジカルソート | 入力 トポロジカルソート | 出力

23章 深さ優先探索

2020/05/17
深さ優先探索
深さ優先探索 ★★
適当な始点から出発し、グラフの全てのノードを体系的に訪問してください。
深さ優先探索 | 入力 深さ優先探索 | 出力
2020/05/17
連結成分分解
DFSによる連結成分分解 ★★
グラフを連携成分に分解して、連結成分内のノードに同じ色を塗ってください。
連結成分分解 | 入力 連結成分分解 | 出力
2020/05/17
DFSによる経路検知
DFSによる閉路検知 ★★
有向グラフに閉路があるかどうかチェックしてください。
閉路検知 | 入力 閉路検知 | 出力
2020/05/17
Tarjanのアルゴリズム
Tarjanのアルゴリズム ★★
タスクと依存関係を表す有向グラフから、タスクを処理する順番を求めてください。
トポロジカルソート | 入力 トポロジカルソート | 出力

24章 Union-Find 木

2020/04/19
ランクによる合併
ランクによる合併
森とそれに含まれる木の根の組がいくつか与えられるので、それらの根で木を合併して森を再構築してください。
木の合併 | 入力 木の合併 | 出力
2020/04/19
経路圧縮
経路圧縮 ★★
森の木を変型して、その高さを縮小してください。
経路圧縮 | 入力 経路圧縮 | 出力
2020/04/19
Union-Find 木
Union-Find 木 ★★★
互いに素な集合を管理するデータ構造を実装してください。
Union-Find | 入力
Union_Find | 出力

25章 最小全域木を求めるアルゴリズム

2020/05/17
プリムのアルゴリズム
プリムのアルゴリズム ★★
重み付き無向グラフの最小全域木を求めてください。
最小全域木 | 入力 最小全域木 | 出力
2020/05/17
クラスカルのアルゴリズム
クラスカルのアルゴリズム ★★★
重み付き無向グラフの最小全域木を求めてください。
最小全域木 | 入力 最小全域木 | 出力

26章 最短経路を求めるアルゴリズム

2020/05/17
ダイクストラのアルゴリズム
ダイクストラのアルゴリズム ★★
重み付きグラフと始点・終点が与えられたとき、始点から終点への最短経路を求めてください。
最短経路問題 | 入力 最短経路問題 | 出力
2020/05/17
ダイクストラのアルゴリズム
ダイクストラのアルゴリズム(優先度付きキュー) ★★★
重み付きグラフと始点・終点が与えられたとき、始点から終点への最短距離を求めてください。
最短経路問題 | 入力 最短経路問題 | 出力
2020/05/17
ベルマンフォードのアルゴリズム
ベルマンフォードのアルゴリズム ★★★
重み付きグラフと始点・終点が与えられたとき、始点から終点への最短距離を求めてください。
最短経路問題(負の重み) | 入力 最短経路問題(負の重み) | 出力
2020/05/17
ワーシャルフロイドのアルゴリズム
ワーシャルフロイドのアルゴリズム ★★★
重み付き有向グラフの隣接行列から、ノードの全ての組についての、最短距離を表す行列を求めてください。
全対点間最短経路 | 入力 全対点間最短経路 | 出力

27章 計算幾何学

2020/05/17
ギフトラッピング
ギフトラッピング ★★
与えられた点の集合の、凸包を求めてください。
凸包 | 入力 凸包 | 出力
2020/05/17
グラハムスキャン
グラハムスキャン ★★★
与えられた点の集合の、凸包を求めてください。
凸包 | 入力 凸包 | 出力
2020/05/17
アンドリューのアルゴリズム
アンドリューのアルゴリズム ★★★
与えられた点の集合の、凸包を求めてください。
凸包 | 入力 凸包 | 出力

28章 セグメント木

2020/05/17
セグメント木:RMQ
セグメント木: RMQ ★★★
整数の列に対して、1要素の更新と区間の最小値検索に対応するデータ構造を実装してください。
Range Minimum Query | 入力
Range Minimum Query | 出力
2020/05/17
セグメント木:RSQ
セグメント木: RSQ ★★★
整数の列に対して、1要素に対する加算と区間の和の計算に対応するデータ構造を実装してください。
Range Sum Query | 入力
Range Sum Query | 出力

29章 探索木

2020/05/17
二分探索木
二分探索木 ★★★
データの検索・追加・削除に加え、整列済みの要素の管理・提供を行う、辞書のデータ構造を実装してください。
整列された辞書 | 入力
整列された辞書 | 出力
2020/05/17
回転
回転 ★★
部分木を変型してください。ただし、変換前後で、中間順巡回で得られるノードの訪問順は変わらないものとします。
回転 | 入力 回転 | 出力
2020/05/17
トリープ
トリープ ★★★★
データの検索・追加・削除に加え、整列済みの要素の管理・提供を行う、辞書のデータ構造を実装してください。
整列された辞書 | 入力
整列された辞書 | 出力

本書に掲載できなかったアルゴリズム




Last Update: