分割統治法とは？

分割統治法とは、大きな問題を、同じ形をしたより小さな複数の部分問題に分割し、それぞれを（多くは再帰的に）解いてから、その結果を組み合わせて元の問題の解を得る手法。マージソートやクイックソート、二分探索法もこの考え方に基づく。

応用情報技術者試験の過去問では2回出題されています（2019年度〜2021年度）。

ぶんかつとうちほう

応用情報技術者試験の頻出用語／テクノロジ系

分割統治法の意味

大きな問題を、同じ形をしたより小さな複数の部分問題に分割し、それぞれを（多くは再帰的に）解いてから、その結果を組み合わせて元の問題の解を得る手法。マージソートやクイックソート、二分探索法もこの考え方に基づく。

マージソートは、データ列を半分に分割することを繰り返し（分割）、十分小さくなった単位を整列してから、隣り合う整列済みの列を1つに統合していく（統治）ことで全体を整列する。

動的計画法との違いは、分割統治法が基本的に部分問題同士が独立している（重複がない）のに対し、動的計画法は同じ部分問題が繰り返し現れる場合に、その結果を再利用する点にある。

分割統治を利用した整列法はどれか。
正解：クイックソート
要点：クイックソートはピボットで2分割して再帰する分割統治法
分割統治法は、問題を小さな部分問題に分割し、それぞれを解いてから統合する考え方です。クイックソートは基準値（ピボット）で列を2つに分割し、各部分を再帰的に整列するため分割統治に該当します。マージソートも同じく分割統治型です。
出典：令和1年度秋期応用情報技術者試験午前問8（IPA）
アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。
正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。
要点：分割統治法は小問題に分けて解き結果を統合する
分割統治法は、問題を同種の小さな部分問題に分割し、それぞれを独立に（多くは再帰的に）解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、高速フーリエ変換などが代表例である。
出典：令和3年度春期応用情報技術者試験午前問7（IPA）

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