分割統治のテンプレート
merge sortから3段階のテンプレート（分割、征服、統合）を抽出し、新しい問題の形に体系的に適用します。
「分割統治のテンプレート」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
分割統治法とは
分割統治法（D&C）は、問題を同じ種類の独立した部分問題に分割し、それぞれを再帰的に解いてから、解を結合することで問題を解決します。重要なキーワードは独立です。部分問題は状態を共有しません（部分問題が重複するDPとは異なります）。代表的な例には、マージソート、二分探索、クイックソート、最近傍点対、行列の高速乗算があります。分割統治法は通常、この3段階のテンプレートによってO(n log n)の時間計算量を実現します。
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]3段階のテンプレート
すべての分割統治アルゴリズムは、次の3段階に従います。(1) 分割 — 問題を、通常は中央で、2つ（またはそれ以上）の小さな部分問題に分けます。(2) 統治 — 各部分問題を再帰的に解きます。再帰を停止するためのベースケースを定義します（通常はn ≤ 1です）。(3) 結合 — 部分問題の解をマージまたは結合して、全体の解を作ります。工夫が必要なのは完全に結合の段階です。分割は通常、中央で分けるだけです。
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)代表例としてのマージソート
マージソートは分割統治法を完全に示す例です。配列を中央で分割します。各半分を再帰的にソートして統治します。ソート済みの2つの半分をO(n)でマージして結合します。すべての処理はマージの段階で行われます。漸化式はT(n) = 2T(n/2) + O(n)です。マスター定理のケース2より、T(n) = O(n log n)です。これは、最も重要な分割統治法の漸化式なので、必ず覚えておきましょう。
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]マスター定理クイックリファレンス
マスター定理は、T(n) = aT(n/b) + f(n)の形の漸化式を解きます。ケース1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a))。ケース2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n)。ケース3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n))。マージソートでは、a=2、b=2、f(n)=O(n)、n^log_2(2)=nなので、ケース2となり、O(n log n)です。
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)最大部分配列: 分割統治法によるアプローチ
最大部分配列に対する分割統治法のアプローチでは、答えは左半分に完全に含まれるか、右半分に完全に含まれるか、中央をまたぐかのいずれかです。中央をまたぐ場合は、midから左方向、mid+1から右方向へ広げ、それぞれの方向で最大の合計を求めてから結合します。このO(n log n)の分割統治法はKadane'sのO(n)より遅いものの、テンプレートを明確に示す美しい例であり、分割統治法に関する面接でよく出る問題です。
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6べき乗関数: 高速べき乗法
Fast Power（LeetCode 50）では、D&Cを使ってx^nをO(log n)で計算します。nが偶数の場合は、x^n = (x^(n/2))^2です。nが奇数の場合は、x^n = x × x^(n-1)です。nが負の場合は、x^(-n) = 1/x^nとして処理します。各再帰呼び出しでnが半分になるため、深さはO(log n)です。結合の段階が単なる乗算という、単純でありながら効果的な例です。
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1ソート済み配列からBSTへ
Convert Sorted Array to BST（LeetCode 108）では、分割統治法を使います。中央の要素をルートにして高さのバランスを保ち、左半分から左部分木を、右半分から右部分木を再帰的に構築します。これにより、最小の高さがO(log n)である高さ平衡BSTが生成されます。分割統治法の構造は二分探索に対応しており、再帰の各レベルで、現在の部分範囲の中央要素をルートに設定します。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)分割統治法が最適とは限らない場合
分割統治法には、関数呼び出しスタックの深さ、配列のスライス（インデックスを使わない場合）、結合の処理といったオーバーヘッドがあります。結合の処理がO(n)以下の場合に最適です。部分問題が重複している場合、分割統治法では解を無駄に再計算するため、DPが必要です。結合の処理が支配的な場合（例: O(n²)）、分割統治法を使っても素朴なアプローチより改善されません。使い分けを理解しておきましょう。独立した部分問題には分割統治法、重複する部分問題にはDPを使います。
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!ソート済み行列の二分探索における分割統治法
各行と各列がソートされている2次元行列の探索（LeetCode 240）は、分割統治法で解けます。右上隅から開始します。現在の値がtargetより大きければ左に移動して列を除外し、現在の値がtargetより小さければ下に移動して行を除外します。等しければ見つかったことになります。このO(m+n)のアルゴリズムは、厳密には再帰的な分割統治法ではありませんが、各ステップで探索空間の半分を除外するという重要な考え方を共有しています。
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # False再帰木による分析
マスター定理に当てはまらない分割統治法の漸化式には、再帰木の手法を使います。再帰呼び出しの各レベルを描き、各レベルの処理量を合計します。マージソートでは、レベルkに2^k個のサイズn/2^kの部分問題があります。各レベルの処理量は2^k × O(n/2^k) = O(n)です。レベルの総数はlog nです。したがって、総処理量はO(n log n)です。この視覚的な手法は、どのような漸化式にも使うことができ、分割統治法が通常O(n log n)になる理由への直感を養えます。
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')分割統治法の面接での説明
面接で分割統治法の解法を説明するときは、次の点を意識します。(1) 3つの段階を明確に述べます。「中央で分割し、各半分を再帰的に解き、最後にマージして結合します」と説明します。(2) ベースケースを明確にします。(3) 漸化式を導出します: T(n) = 2T(n/2) + O(n)。(4) マスター定理または再帰木を適用してO(n log n)を導出します。(5) 他の方法と比べて分割統治法が優れている場合と劣る場合（重複する部分問題にはDP、最大部分配列にはKadane's）について説明します。
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、分割統治法は、ベースケース → 中央で分割 → 再帰的に統治 → 結合というテンプレートに従います、T(n) = 2T(n/2) + O(n)は、マスター定理のケース2によりO(n log n)になります、そして分割統治法は独立した部分問題に最適であり、部分問題が重複する場合にはDPが必要ですということを学びました。次は、マージソートを変更して配列の転倒数を数えるために、分割統治法を適用します。
よくある質問
「分割統治のテンプレート」レッスンは無料ですか？
はい。「分割統治のテンプレート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「分割統治のテンプレート」で何を学びますか？
merge sortから3段階のテンプレート（分割、征服、統合）を抽出し、新しい問題の形に体系的に適用します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「分割統治のテンプレート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。