분할 정복

🎯 학습 목표

이 강을 마치면 분할 정복을 분할 → 정복 → 결합 세 단계로 설계할 수 있습니다. 그리고 이 전략이 어떤 조건에서 복잡도를 낮추는지, 반대로 언제 효과가 없는지를 판단할 수 있게 됩니다.

9강 병합 정렬에서 이미 분할 정복을 봤습니다. 이번에는 그것을 일반 전략으로 정리하고, 거듭제곱을 O(log n)에 계산하는 등 정렬 외의 활용을 다룹니다.

💡 세 단계 — 분할, 정복, 결합

분할 정복(divide and conquer)은 문제를 작은 같은 모양의 문제로 쪼개고, 각각 푼 뒤, 결과를 합치는 전략입니다.

세 단계

  ① 분할 (Divide)
     문제를 더 작은 부분 문제로 나눈다
     · 절반으로 나누는 경우가 가장 흔하다
     · 몇 개로 나누는지가 복잡도를 결정한다

  ② 정복 (Conquer)
     부분 문제를 재귀로 푼다
     · 충분히 작아지면 기저 조건에서 직접 푼다 (13강)

  ③ 결합 (Combine)
     부분 답을 합쳐 전체 답을 만든다
     · 이 비용이 전체 복잡도를 좌우한다  ★

  ▲ 복잡도가 정해지는 방식

    T(n) = (부분 문제 개수) × T(n / 나눈 비율) + (결합 비용)

    병합 정렬
      T(n) = 2 × T(n/2) + O(n)   → O(n log n)
      2개로 쪼개고, 합칠 때 n번 훑는다

    이분 탐색 (10강)
      T(n) = 1 × T(n/2) + O(1)   → O(log n)
      한쪽만 보고, 합칠 것이 없다

    거듭제곱 (아래 예제)
      T(n) = 1 × T(n/2) + O(1)   → O(log n)

  ▲ 여기서 핵심 통찰
    쪼갠 뒤 '한쪽만' 보면 log n
    쪼갠 뒤 '양쪽 다' 보면서 합치면 n log n

이 관계를 보면 왜 이분 탐색이 O(log n)이고 병합 정렬이 O(n log n)인지가 한눈에 정리됩니다. 둘 다 절반씩 쪼개지만 버리느냐 합치느냐가 다릅니다.

📖 언제 효과가 있고 언제 없는가

분할 정복이 항상 이득은 아닙니다. 세 가지 조건을 확인해야 합니다.

조건	내용	안 맞으면
독립성	부분 문제가 서로 영향을 주지 않는다	DP로 가야 함(26강)
동일성	부분 문제가 원래 문제와 같은 모양	재귀로 표현 불가
결합 가능	부분 답으로 전체 답을 만들 수 있다	전략 자체가 성립 안 함

분할 정복 vs 동적 계획법

  [분할 정복]  부분 문제가 겹치지 않는다
    병합 정렬에서 왼쪽 절반과 오른쪽 절반은
    완전히 다른 데이터다 → 중복 계산이 없다

  [동적 계획법]  부분 문제가 겹친다
    피보나치에서 fib(3) 이 여러 번 필요하다 (13강)
    → 저장해 두고 재사용해야 한다

  ▲ 판단 기준
    "같은 부분 문제를 두 번 이상 푸는가?"
     아니오 → 분할 정복
     예     → 동적 계획법 (메모이제이션)

  ▲ 효과가 없는 경우

   ① 결합 비용이 너무 크다
      합치는 데 O(n²)가 들면
      T(n) = 2T(n/2) + O(n²) → O(n²)
      쪼갠 의미가 사라진다

   ② n이 작다
      재귀 호출 비용이 오히려 크다
      → 실제 정렬 구현들이 작은 구간에서
        삽입 정렬로 전환하는 이유 (9강)

   ③ 부분 문제가 줄지 않는다
      T(n) = 2T(n-1) + O(1) → O(2ⁿ)
      절반이 아니라 1씩 줄면 지수가 된다

💻 실전 예제 — 거듭제곱과 최대 부분합

def power(base, exp):
    """base^exp 를 O(log exp) 에 계산"""
    if exp == 0:                      # 기저 조건
        return 1
    half = power(base, exp // 2)      # 절반만 계산한다  ★
    if exp % 2 == 0:
        return half * half            # 짝수: (b^(n/2))^2
    return half * half * base         # 홀수: 하나 더 곱한다


def max_subarray(nums, left, right):
    """최대 부분합을 분할 정복으로 → O(n log n)"""
    if left == right:                 # 기저 조건: 원소 하나
        return nums[left]

    mid = (left + right) // 2
    left_best = max_subarray(nums, left, mid)        # 왼쪽에만 있는 경우
    right_best = max_subarray(nums, mid + 1, right)  # 오른쪽에만 있는 경우

    # 중앙을 걸치는 경우: 가운데에서 양쪽으로 뻗어 나간다
    total = 0
    left_part = float("-inf")
    for i in range(mid, left - 1, -1):
        total += nums[i]
        left_part = max(left_part, total)

    total = 0
    right_part = float("-inf")
    for i in range(mid + 1, right + 1):
        total += nums[i]
        right_part = max(right_part, total)

    return max(left_best, right_best, left_part + right_part)


print(power(2, 10))                   # 1024
print(power(3, 13))                   # 1594323
data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(data, 0, len(data) - 1))   # 6  ([4,-1,2,1])

코드를 줄 단위로 보겠습니다.

• half = power(base, exp // 2) — 이 강의 핵심입니다. power(base, exp-1)을 부르면 O(n)이지만, 절반을 한 번만 계산해 재사용하면 O(log n)이 됩니다.
• return half * half — power(base, exp//2) * power(base, exp//2)라고 쓰면 두 번 계산하게 되어 O(n)으로 돌아갑니다. 반드시 변수에 담아 재사용해야 합니다.
• if exp % 2 == 0 — 짝수면 제곱만, 홀수면 밑을 한 번 더 곱합니다. 2^5 = (2^2)^2 × 2입니다.
• if left == right: return nums[left] — 구간에 원소가 하나면 그 값이 답입니다.
• mid = (left + right) // 2 — 구간을 인덱스로 나눕니다. 13강에서 말한 대로 슬라이싱하지 않아 복사 비용이 없습니다.
• for i in range(mid, left - 1, -1) — 가운데에서 왼쪽으로 뻗어 가며 최대 합을 찾습니다. range의 세 번째 인자 -1이 감소 방향을 뜻합니다.
• float("-inf") — 음의 무한대입니다. 배열에 음수만 있어도 올바르게 동작하도록 초기값을 잡는 방법입니다. 0으로 초기화하면 전부 음수인 입력에서 답이 틀립니다.
• left_part + right_part — 중앙을 걸치는 구간은 반드시 mid와 mid+1을 모두 포함하므로 양쪽 최대를 더하면 됩니다.

max_subarray는 O(n log n)입니다. 참고로 이 문제는 동적 계획법으로 O(n)에 풀 수 있습니다(26강). 분할 정복이 항상 최선은 아니라는 좋은 예입니다.

power의 활용도는 높습니다. 거듭제곱을 나머지 연산과 함께 쓰는 문제(모듈러 거듭제곱)에서 그대로 쓰이고, 행렬 거듭제곱으로 피보나치를 O(log n)에 구하는 기법의 토대이기도 합니다.

⚠️ 자주 하는 실수

첫째, 재귀 호출을 두 번 합니다. power에서 half를 변수에 담지 않고 두 번 호출하면 O(log n)이 O(n)이 됩니다. 13강 피보나치와 같은 함정입니다. 같은 값을 두 번 계산하지 않는지 항상 확인하세요.

둘째, 슬라이싱으로 분할합니다. f(arr[:mid])는 매번 O(n) 복사가 일어납니다. 인덱스 범위를 인자로 넘기면 복사가 사라집니다.

셋째, 결합 단계를 빠뜨립니다. 최대 부분합에서 중앙을 걸치는 경우를 빼먹으면 답이 틀립니다. 분할 정복에서는 "경계에 걸친 답"을 항상 따로 챙겨야 합니다.

넷째, 초기값을 0으로 둡니다. 최댓값을 구할 때 0으로 시작하면 모든 값이 음수인 입력에서 0을 답으로 내놓습니다. float("-inf")나 첫 원소로 시작하세요.

다섯째, 겹치는 부분 문제에 분할 정복을 씁니다. 같은 부분 문제를 반복해서 푼다면 메모이제이션을 붙이거나 DP로 전환해야 합니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	분할 → 정복 → 결합
2	복잡도 = 부분 개수 × T(n/비율) + 결합 비용
3	쪼갠 뒤 한쪽만 보면 log n, 합치면 n log n
4	결합 비용이 전체를 좌우한다
5	부분 문제가 겹치면 DP, 안 겹치면 분할 정복
6	같은 값을 두 번 계산하지 않는다
7	분할은 인덱스로, 슬라이싱 금지

지금 해 볼 것은 power에서 half를 쓰지 않고 power(base, exp//2) * power(base, exp//2)로 바꿔 power(2, 30)을 실행해 보는 것입니다. 눈에 띄게 느려지는 것을 보면 "재사용"의 의미가 확실해집니다.

다음 15강 「완전 탐색」에서는 모든 경우를 다 해 보는 접근을 다룹니다. 무식해 보이지만 입력이 작으면 가장 확실한 방법이고, 2강에서 배운 입력 범위 역산이 여기서 결정적으로 쓰입니다.

📚 참고 자료

• pow() — Python 공식 문서
• range() — Python 공식 문서
• float() — Python 공식 문서