分割統治法パターン

中級

カテゴリ: arrays

概要

分割統治法（Divide and Conquer）は、複雑な問題を同じ形式のより小さな部分問題に分割し、それらを解いた後、部分解を組み合わせて元の問題の解を得るアルゴリズム設計パラダイムです。このアプローチは3つの主要なステップから成ります：1) 分割（Divide）：問題をより小さな部分問題に分割、2) 統治（Conquer）：部分問題を再帰的に解く、3) 結合（Combine）：部分解を組み合わせて元の問題の解を形成。分割統治法は多くの効率的なアルゴリズムの基礎となっており、並列処理にも適しています。

コードテンプレート

Java

Python

- 分割統治法の一般的なテンプレート
public Result divideAndConquer(Problem problem) {
    // 基本ケース: 問題が十分に小さい場合は直接解く
    if (problem.size() <= THRESHOLD) {
        return solveDirect(problem);
    }
    
    // 分割: 問題をより小さな部分問題に分割
    Problem[] subproblems = divide(problem);
    
    // 統治: 各部分問題を再帰的に解く
    Result[] subresults = new Result[subproblems.length];
    for (int i = 0; i < subproblems.length; i++) {
        subresults[i] = divideAndConquer(subproblems[i]);
    }
    
    // 結合: 部分解を組み合わせて元の問題の解を形成
    return combine(subresults);
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

分割統治結合再帰部分問題マージソートクイックソート二分探索並列処理マスター定理部分解独立した部分問題効率的なアルゴリズム問題分割再帰的解法分割統治

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
マージソート（Merge Sort）: 配列を半分に分割し、各部分をソートした後、マージする
2
クイックソート（Quick Sort）: ピボットを選び、配列を分割してソートする
3
二分探索（Binary Search）: 探索範囲を半分に分割して探索を続ける
4
最大部分配列問題（Maximum Subarray）: 配列を分割して最大部分配列を見つける
5
ストラッセンのアルゴリズム（Strassen's Algorithm）: 行列乗算を効率的に行う
6
最近点対問題（Closest Pair of Points）: 平面上の最も近い2点を見つける
7
高速フーリエ変換（Fast Fourier Transform）: 信号処理や多項式乗算に使用

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

中

ピーク要素を見つける

整数の配列 nums が与えられます。ピーク要素とは、その隣接する要素よりも大きい要素のことです。配列の最初と最後の要素は隣接要素がないため、それぞれ -∞ と比較されます。ピーク要素のインデック...