アルゴリズム 【深さ優先探索】DFSによる全探索を理解したい!(Atcoder ABC119 C解説)【Python】 AtcoderのABC119 C - Synthetic Kadomatsuは深さ優先探索(DFS)による全探索を修得するのに適した問題である。DFSの視覚的なイメージや漸化式を含めて解説する。 2022.09.03 アルゴリズム
アルゴリズム 【幅優先探索】木構造(グラフ)における頂点間距離を求める【Python】 木構造を扱う際、頂点間の距離や根からの距離を求めたり、木の直径を求めたりする場面があります。本記事では幅優先探索(BFS)の考え方を図で直感的にイメージした後、グラフ(木構造)の頂点間の距離に関する具体的な問題を解説しています。 2022.08.12 アルゴリズム
アルゴリズム 【深さ優先探索】グラフの連結判定(AtCoderABC259 D問題解説) Pythonでグラフの連結判定問題を詳細に解説します。グラフ理論・連結性判定に関する良問、AtCoderABCコンテスト259D問題を例に解説します。隣接行列・深さ優先探索の実装など得るものが多い問題です。 2022.07.12 アルゴリズム
アルゴリズム 【AtCoder】C問題をPythonで全制覇する(ABC042~099)【解説・分類】 本記事ではAtCoderABCコンテストC問題について、考え方とPythonでの解答を紹介しています。汎用的でシンプルな解き方を心掛けています。また、辞書的に利用できるよう、各問題に分類を記載しました。Ctrl + F で問題をキーワード検索できます。 2022.07.03 アルゴリズム
アルゴリズム 【動的計画法】最長部分増加列を典型問題でマスターしよう(Python) 本記事では、動的計画法を用いて最長増加部分列の長さを求める問題を取り扱う。直感的に理解しやすいアルゴリズムに加え、二分探索を導入して計算量をO(NlogN)に抑えるアルゴリズムについても徹底解説している。図や具体例を用いて、じっくり理解したい方におすすめ。 2022.05.27 アルゴリズム
アルゴリズム 【動的計画法】DPで最安値問題を解く(Python) 動的計画法(DP)の練習として、最安値問題は適切な難易度の問題だ。本記事では、例題を通してDPアルゴリズムの基礎を理解していく。 2022.05.26 アルゴリズム
アルゴリズム 【二分探索(応用編)】最大値の最小化・最小値の最大化問題を解く(Python) 本記事では、2分探索の典型的な問題について、Pythonでの実装例を紹介する。「単調性」を利用した考え方を、いかにコードに落とし込むのか、図や数式を用いて解説している。 2022.05.24 アルゴリズム
アルゴリズム 【二分探索(基礎編)】値の探索、境界値・範囲を求める(Python) 本記事では、2分探索の典型的な問題について、Pythonでの実装例を紹介している。これを読めば、昇順に並んだリストを対象に、値の探索・境界値を求める・範囲を求めるといった二分探索に関する問題を解くことができるようになるだろう。 2022.05.19 アルゴリズム
アルゴリズム 【動的計画法】部分和問題の典型パターン4種類の問題を解く(Python) 私がアルゴリズムの勉強を始めてから、最初にぶつかったのが、動的計画法(DP)でした。深く理解するために、具体例を用いて、これでもかという程に詳しく解説したつもりです。ここでは、動的計画法を用いて、様々なタイプの部分和問題(ナップサック問題に類似している問題)を解く方法を解説します。 2022.05.04 アルゴリズム