分割統治法とは？ぶんかつとうちほう
分割統治法とは、問題を同種の小さな部分問題に分割して解き、その結果を統合して全体の解を得る設計手法。再帰と組み合わせて使われることが多い。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
マージソートは配列を半分ずつに分けて整列し、整列済みの2つを併合する。クイックソートや高速フーリエ変換も分割統治法に分類される。
試験での引っ掛け
「動的計画法」は部分問題の答えを表に記録して再利用する点が異なる。分割統治では部分問題が重複しないことが前提。
関連用語
出た過去問
出典：令和3年度 春期 高度試験 午前Ⅰ 問3（IPA）
アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。
正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。
要点：分割統治法は小問題に分けて解き結果を統合する
分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (3) アルゴリズム設計に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。