Pythonで順列全探索を実装してみる-ABC150

本記事では順列全探索をPythonで実装していきます。Pythonではitertoolsを使うことで簡単に順列を生成することができます。 順列全探索とは 例題 問題文 制約 実装 まとめ 順列全探索とは 順列全探索とは通りの順列の組み合わせを全探索する手法です。例えば、(1, 2, 3)の組み合わせはなので全部で9種類あります。 9種類の組み合わせはこのようになります。 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]順列は再帰関数を利用することによって自分で一から実装することもできますが、Pythonの場合は…

Pythonで解くナップサック問題【動的計画法（DP）入門】

この記事では競技プログラミング等で頻出のアルゴリズムである「動的計画法」をナップサック問題を通して解説していきます。まず動的計画法についての解説をしてから、実際にナップサック問題をPythonで解いていきます。 そもそも動的計画法（DP）とは ナップサック問題を解こう 問題文 実装 まとめ (adsbygoogle = window.adsbygoogle []).push({}); そもそも動的計画法（DP）とは 動的計画法を簡単に説明すると「問題を分割して計算結果を記録しながら解いていく手法」です。細かく定義されているアルゴリズムではないので一言で動的計画法といっても種類がいくつかあ…