分割統治法とは？

分割統治法とは、問題を同種の小さな部分問題に分割して解き、その結果を統合して全体の解を得る設計手法。再帰と組み合わせて使われることが多い。

高度試験・午前I（全区分共通）の過去問では1回出題されています。

ぶんかつとうちほう

高度試験・午前I（全区分共通）の頻出用語／午前I（全区分共通）

分割統治法の意味

問題を同種の小さな部分問題に分割して解き、その結果を統合して全体の解を得る設計手法。再帰と組み合わせて使われることが多い。

マージソートは配列を半分ずつに分けて整列し、整列済みの2つを併合する。クイックソートや高速フーリエ変換も分割統治法に分類される。

「動的計画法」は部分問題の答えを表に記録して再利用する点が異なる。分割統治では部分問題が重複しないことが前提。

アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。
正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。
要点：分割統治法は小問題に分けて解き結果を統合する
分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。
出典：令和3年度春期高度共通_午前I試験 am1 問3（IPA）

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。