エンジニアとしての強み

各カテゴリの詳細を確認できます

アルゴリズム

習得しているアルゴリズムとその使える度について紹介します。

実績

競技プログラミングでの経験

学生時代にAtCoderで黄色（上位〜3%）に到達する過程で、様々なアルゴリズムを学習し実装してきました。競技プログラミングを通じて培った問題解決能力と実装スキルは、実務でのソフトウェア開発にも大いに役立っています。

使える度の凡例

各レベルの意味は以下の通りです

レベル	説明
0	使ったことがないまたは使えない
1	内容は理解はしていないが使うことはできる
2	アルゴリズムの手順を理解している
3	調べれば証明を説明できる、自力で実装できる

基本テクニック

問題解決の基礎となる基本的なアルゴリズムとテクニック

アルゴリズム名	内容	使える度
全探索	すべての可能性を調べる基本的なアルゴリズム。実装が簡単で確実な解を得られる。
集合全探索	ビット演算を用いて部分集合を効率的に列挙するテクニック。2^N通りの組み合わせを探索できる。
二分探索	ソート済み配列から目的の値を効率的に探すアルゴリズム。O(log N)の計算量で動作する。
三分探索	上に凸または下に凸な関数の極値を効率的に求めるアルゴリズム。
累積和	配列の部分和を高速に計算するためのテクニック。区間クエリに対してO(1)で応答できる。
いもす法	区間に対する加算操作を効率的に処理するアルゴリズム。区間加算クエリをO(1)で処理できる。
尺取り法	配列上の条件を満たす区間を効率的に探索するテクニック。O(N)の計算量で動作する。
再帰	関数が自分自身を呼び出すプログラミング手法。多くのアルゴリズムの基礎となる。
末尾再帰	再帰呼び出しが関数の最後の操作となる最適化された再帰。スタックオーバーフローを防ぐ。
ソート	データを特定の順序に並べ替えるアルゴリズム。様々な実装方法がある。
貪欲法	その場その場で最適な選択を行う問題解決アプローチ。問題によって最適解を得られるとは限らない。

数学的アルゴリズム

数学的な問題を解くためのアルゴリズム

アルゴリズム名	内容	使える度
素数判定/エラトステネスの篩	素数を効率的に判定・列挙するアルゴリズム。多数の素数を扱う問題で有用。
約数列挙	数の約数を効率的に列挙するアルゴリズム。O(√N)の計算量で動作する。
拡張ユークリッドの互除法	ax + by = gcd(a,b)の整数解を求めるアルゴリズム。モジュラ逆元の計算などに利用される。
繰り返し二乗法	a^nを効率的に計算するアルゴリズム。O(log N)の計算量で動作する。
包除原理	複数の集合の和集合の要素数を計算するための数学的原理。
行列累乗	行列のn乗を効率的に計算するアルゴリズム。線形漸化式の高速計算などに利用される。
高速フーリエ変換(FFT)/高速数論変換(NTT)	多項式の乗算を効率的に計算するアルゴリズム。O(N log N)の計算量で動作する。

データ構造

データを効率的に管理するための構造

アルゴリズム名	内容	使える度
スタック/キュー/両端キュー	基本的なデータ構造。それぞれLIFO、FIFO、両端からの挿入削除が可能。
連装配列/集合/多重集合	要素の集まりを管理するデータ構造。検索、挿入、削除などの操作が可能。
優先度付きキュー/ヒープ	最小値または最大値を効率的に取り出せるデータ構造。O(log N)で操作可能。
フィボナッチヒープ	優先度付きキューの一種。理論的には多くの操作が償却定数時間で実行可能。
Union-Find(DSU)	素集合を管理するデータ構造。要素の併合と同じ集合に属するか判定が高速。
セグメント木	区間に対する様々な演算を効率的に行うデータ構造。O(log N)で操作可能。
遅延評価セグメント木	区間更新と区間クエリを両立するセグメント木の拡張。
区間作用素付きセグメント木	複雑な区間操作に対応するセグメント木の拡張。
フェニック木	累積和の更新と計算を効率的に行うデータ構造。O(log N)で操作可能。
Trie木/パトリシア木	文字列の集合を効率的に管理するための木構造。前方一致検索などに有用。

グラフアルゴリズム

グラフ理論に基づく問題解決アルゴリズム

アルゴリズム名	内容	使える度
グラフ表現(隣接リスト、隣接行列)	グラフを表現するための基本的な方法。問題に応じて適切な表現を選択する。
幅優先探索	グラフの頂点を幅優先で探索するアルゴリズム。最短経路問題などに利用される。
深さ優先探索	グラフの頂点を深さ優先で探索するアルゴリズム。連結成分の検出などに利用される。
ダイクストラ法	重み付きグラフの単一始点最短経路を求めるアルゴリズム。負の辺がない場合に使用。
ベルマン・フォード法	重み付きグラフの単一始点最短経路を求めるアルゴリズム。負の辺がある場合にも使用可能。
ワーシャル・フロイド法	全点対間の最短経路を求めるアルゴリズム。O(V^3)の計算量で動作する。
最小全域木	グラフの全ての頂点を結ぶ最小コストの木を求めるアルゴリズム。クラスカル法やプリム法がある。
最小有効全域木	有向グラフにおける最小全域木を求めるアルゴリズム。
トポロジカルソート	有向非巡回グラフの頂点を依存関係に従って並べるアルゴリズム。
強連結成分分解	有向グラフを強連結成分に分解するアルゴリズム。
二重辺連結成分分解	無向グラフを二重辺連結成分に分解するアルゴリズム。
二重頂点連結成分分解	無向グラフを二重頂点連結成分に分解するアルゴリズム。
二部グラフ判定	グラフが二部グラフであるかを判定するアルゴリズム。
最大フロー(フォード・ファルカーソン法)	ネットワークの最大フローを求めるアルゴリズム。
最大フロー(Dinic/Relabel-Push/...etc)	より効率的な最大フローアルゴリズム。
最小費用流	コストが最小となるフローを求めるアルゴリズム。

動的計画法

部分問題の解を再利用する効率的な問題解決手法

アルゴリズム名	内容	使える度
ナップザックDP	重さと価値を持つ品物から、制限内で最大の価値を得る組み合わせを求める問題。
区間DP(Monge)	区間に対する最適解を部分問題から構築する動的計画法。
桁DP	数の桁に着目した動的計画法。数え上げ問題などに利用される。
集合DP	集合を状態とする動的計画法。ビット演算を用いて実装されることが多い。
全方位木DP	木上で任意の頂点を根とした場合の解を効率的に計算する手法。
挿入DP	要素の挿入順序に着目した動的計画法。
HLRecDP	高度な再帰的動的計画法。

文字列アルゴリズム

文字列処理に特化したアルゴリズム

アルゴリズム名	内容	使える度
ローリングハッシュ	文字列を数値に変換し、高速に比較するハッシュ法。部分文字列の一致判定などに利用。
KMP法	文字列パターンマッチングを効率的に行うアルゴリズム。O(N+M)の計算量で動作。
Z-algorithm	文字列の各位置から始まる最長の接頭辞を効率的に計算するアルゴリズム。

高度なデータ構造

複雑な操作を効率的に行うための発展的なデータ構造

アルゴリズム名	内容	使える度
平衡二分探索木	挿入・削除・検索がO(log N)で行えるバランスの取れた二分探索木。
マージ可能平衡二分探索木	2つの木を効率的にマージできる平衡二分探索木。
モノイドが乗った平衡二分木	各ノードにモノイド演算を適用できる平衡二分探索木。
Convex-Hull-Trick-Add-Monotone	直線の集合に対する最小値クエリを効率的に処理するデータ構造。
Li-Chao-Tree	直線や区分線形関数の集合に対する最小値クエリを処理するデータ構造。
LinkCut木	動的な木に対する様々な操作を効率的に行うデータ構造。
スパーステーブル	静的な配列に対するRMQ（Range Minimum Query）を前計算によりO(1)で処理するデータ構造。
ウェーブレット行列	配列の区間クエリを効率的に処理するデータ構造。ランク・セレクト操作などを高速に実行できる。
永続配列	過去の状態を保持しながら更新可能なデータ構造。
接尾辞配列(Suffix-Array)	文字列の全ての接尾辞をソートしたもの。文字列処理に有用。
HL-Decomposition	木を重い辺と軽い辺に分解し、パス上のクエリを効率的に処理する手法。
形式的冪級数	冪級数を形式的に扱うデータ構造。多項式の演算を効率的に行う。

数値計算

数値解析や科学技術計算のためのアルゴリズム

アルゴリズム名	内容	使える度
ガウスの消去法	連立一次方程式を解くための基本的なアルゴリズム。
LU分解	行列をLU行列に分解する手法。連立方程式を効率的に解くのに利用。
QR法	行列の固有値を数値的に求めるアルゴリズム。
共役勾配法	大規模な疎行列の連立一次方程式を解くための反復法。
ガウス＝ザイデル法	連立一次方程式を解くための反復法。
二分法	方程式の解を区間を半分に分けながら求める数値解法。
ニュートン法	方程式の解を接線を用いて近似的に求める数値解法。収束が速い。
ラグランジュ補完	与えられた点を通る多項式を求める補間法。
スプライン補完	滑らかな曲線で点を補間する手法。
最小二乗法	データ点と近似曲線との誤差の二乗和を最小化する手法。
シンプソン法	関数の定積分を数値的に計算する手法。
ガウス求積法	高精度な数値積分法。
オイラー法	常微分方程式の数値解法。最も基本的な手法。
ルンゲ=クッタ法	常微分方程式の高精度な数値解法。
シンプレックス法	線形計画問題を解くためのアルゴリズム。