問題 No.2758
大きな問題を同じ構造を持つ小さな部分問題に分割し、それぞれの部分問題を再帰的に解いてからそれらの解を統合することで全体を解決するアルゴリズム設計手法を指す用語はどれか。
【正解の解説】
分割統治法
これは巨大なピザを一口サイズに切り分けてからみんなで食べるようなものです。例えば、分厚い辞書を半分ずつに引き裂いて検索範囲を狭め、最終的に答えを合わせる「マージソート」などが代表例で、複雑な問題をスルスルと解きほぐすための強力な考え方です。
スポンサーリンク
【その他の選択肢の解説】
動的計画法
問題文にある「分割して解く」というアプローチ自体は似ていますが、動的計画法は「一度解いた部分問題の答えをメモ帳に記録（メモ化）して再利用する」という点が決定的な違いです。フィボナッチ数列などを効率よく解く際によく使われます。
貪欲法
目の前の一番大きな利益だけを次々と貪欲に選んでいく方法で、全体を小さな部分問題に分割して統治する分割統治法とはアプローチの根本が異なります。例えば、お財布にある硬貨で最少枚数のお釣りを出すときなどに使われます。
深さ優先探索
迷路を解くときに「突き当たりまで進んで、ダメなら一本道戻る」という探索を行う手法であり、アルゴリズムの実装内部で再帰呼び出しが使われることは多いですが、問題全体を分割統治する設計手法そのものを指す言葉ではありません。