令和3年度春期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：分割統治法は“小分けにしてから合体”する考え方だよ

分割統治法は、大きくて手に負えない問題を、ケーキを切り分けるみたいに小さな問題へ分けて、それぞれを解いたあと、最後に結果をまとめる方法だよ。

この問題で問われていること

ポイントは、少しずつ直していく逐次改良法、全部試す全探索、その場で一番よさそうなものを選ぶ貪欲法との違いを見分けられるかだよ。分割統治法は“分ける→解く→まとめる”の流れで考えよう。

Divide and Conquer

divide problem -> solve subproblems -> combine results

divide\nsolve\ncombine

確認ポイント

• その場の最良選択を重ねるのは貪欲法です。
• 全組合せ確認でもない。
• 結合して全体解に戻す。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは不正解だよ。これは、まずざっくりした答えを出して少しずつ良くしていく逐次改良の考え方に近いね。たとえば部屋の模様替えで、最初に家具を仮置きしてから「ここを少し動かそう」と調整していく感じ。分割統治法は、粗い答えを直していく方法ではなく、問題を小さく分けて別々に解き、最後に組み合わせる方法だよ。

選択肢イ

これは不正解だよ。これは分枝限定法に近い説明だね。たとえば合鍵を作る番号を全部試すのは大変だから、「この範囲は絶対違う」と分かった枝を途中で切り捨てる感じ。無駄な組合せを調べないようにする方法であって、分割した小問題を解いて合体する分割統治法とは違うよ。

選択肢ウ（正解）

これは正解だよ。分割統治法は、大きな仕事を小さな仕事に分けて、それぞれを解いてから最後につなげる方法だよ。たとえば大量の書類を一人で全部整理するのではなく、束ごとに分けて別々に整理し、最後に順番どおりまとめる感じ。マージソートみたいに「分ける、解く、合わせる」がポイントだよ。

選択肢エ

これは不正解だよ。これは分割統治法ではなく、貪欲法の考え方だね。たとえば旅行ルートを決めるときに「今いる場所から一番近い観光地へ行こう」を毎回選ぶ感じ。目先では良さそうだけど、全体で一番効率が良いとは限らないよ。分割統治法は、目先の最良を選び続ける方法ではなく、大きな問題を小さく分けて解く方法だよ。