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

動的計画法の備忘録として、問題とその回答コードについてまとめておきます。

pythonで約数列挙のアルゴリズムについて、考え方と実装コードをまとめました。

競技プログラミングを勉強している中で、二次元のグリッドを使った問題と度々出会います。解いた問題の備忘録も兼ねて、問題とその解法についてまとめておきます。

高校数学の場合の数でよく見る、二次元のグリッドの道順総数を解く問題を扱います。この問題を解くための３つのアルゴリズムを紹介します。3つのアルゴリズムとして、動的計画法・メモ化再帰・重複順列を取り上げます。重複順列では数字が大きくなっても対応できるよう、逆元というテクニックについても紹介しています。

二分探索の応用問題の一つとして、条件を満たす値のうち最大のものを探索する問題があります。これに関連するいくつかの問題を取り上げ、判定と範囲の絞り込みの考え方を紹介します。

べき乗の高速な計算アルゴリズムである、繰り返し二乗法に関して解説します。本手法の理解には2進数、シフト演算および論理積の理解が重要なため、これらのことにも解説しています。また、実際にコードを動かした際の挙動についても詳しく見ています。

順列の問題で、辞書順でK番目の列は何か、もしくはある数字列は何番目か問われることがあります。この問題をアルゴリズムを用いて解く方法についてまとめ、pythonのコードを紹介します。

再帰関数やメモ化再帰を自力で実装しようとするとなかなか手が進まない場面が多々ありました。そこで、これらの実装をやりやすくする考え方のフォーマットを紹介し、フィボナッチ数列でデモンストレーションしたいと思います。

メモ化再帰は再帰関数を高速化する方法の一つで、有名な問題に部分和問題があります。この問題を解く過程で自分が書いた失敗コードから、どこが問題なのか、どう直せばいいのかを整理・共有したいと思います。