[알고리즘] 분할 정복(Divide and Conquer)

✅ 분할 정복이란?

분할 정복(Divide and Conquer)은 큰 문제를 더 작고 동일한 형태의 문제로 분할한 뒤, 각각을 재귀적으로 해결하고 그 결과를 결합(merge)하여 전체 문제를 푸는 알고리즘 설계 기법

🔧 핵심 구조

1. Divide : 문제를 더 작은 부분 문제로 나눈다.

2. Conquer : 각 부분 문제를 재귀적으로 해결한다.

3. Combine : 해결된 결과를 결합하여 최종 답을 얻는다.

🎯 분할 정복을 사용해야 하는 문제의 특징

특징	설명
문제를 쪼갤 수 있다	문제를 더 작고 동일한 구조로 나눌 수 있어야 한다
부분 문제의 결과로 원래 문제를 해결할 수 있다	각 부분 문제의 결과를 합쳐 전체 결과를 만들 수 있어야 한다
부분 문제들이 독립적이다	각각의 하위 문제는 다른 문제에 영향을 주지 않고 개별적으로 풀 수 있어야 한다
중복 계산이 거의 없다	동일한 부분 문제를 반복 계산하지 않아도 되는 구조 (DP와 차이점)
전체 문제를 직접 풀기보다 나눠서 푸는 것이 더 효율적이다	시간 복잡도 개선 가능성 있음

📌 수도코드(pseudocode) 구조

함수 divideAndConquer(input):

	// 1. 기저 조건(base case) => 재귀 종료 조건
    if input is small or simple enough:
        return solve(input) // 재귀 없이 직접 처리할 수 있는 가장 작은 단위 문제에 대한 해결 함수

	// 2. 분할 (Divide)
    subInputs = divide(input) // 문제를 더 작은 동일한 형태의 부분 문제로 나누는 함수

	// 3. 정복 (Conquer) => 문제의 핵심 계산이 일어남
    subResults = []
    for sub in subInputs:
        result = divideAndConquer(sub) // 분할된 문제에 대해 재귀적으로 같은 방식으로 해결
        subResults.append(result)

	// 4. 결합 (Combine) => 부분 문제들의 결과를 모아서 전체 문제의 결과로 합침
    return combine(subResults)

✅ 분할 정복 기법을 사용하는 알고리즘

알고리즘	설명
병합 정렬 (Merge Sort)	배열을 반씩 나누고 정렬한 후 병합
퀵 정렬 (Quick Sort)	피벗을 기준으로 분할하며 정렬
이진 탐색 (Binary Search)	정렬된 배열을 반씩 나누며 탐색
거듭제곱 계산 (Exponentiation by Squaring)	수나 행렬을 빠르게 제곱
최대 구간 합 (Divide and Conquer 방식의 Kadane 변형)	배열을 좌우로 나누어 최대 합 찾기
가장 가까운 두 점 문제 (Closest Pair of Points)	2D 평면에서 유클리드 거리 최소 쌍 찾기

⚠️ 주의할 점: 함수 오버헤드

• 분할 정복은 보통 재귀 호출을 사용

• 함수 호출이 많아지면 함수 오버헤드가 성능에 영향을 줄 수 있음

• 다만 대부분의 경우 오버헤드는 무시 가능하며, 코드 가독성과 구조화 측면에서 함수 분리는 유익함

• 오버헤드를 고려해야 하는 상황

  • 재귀 호출이 10⁷~10⁹번 이상인 경우

  • 자바에서 스택 깊이 초과 (StackOverflow) 위험이 있는 경우

    • 일반적인 JVM에서는 약 7,000~10,000 재귀 깊이에서 StackOverflowError 발생

---

🧩 연습문제

문제 번호	문제 이름	설명	풀이 포스팅
BOJ 2630	색종이 만들기	분할 정복으로 영역 색상 확인	풀이 보기 🔗
BOJ 17829	222-풀링	2차원 배열을 반복적으로 압축하는 분할 정복 문제	풀이 보기 🔗
BOJ 1992	쿼드트리	2차원 분할 정복 구조 익히기	풀이 보기 🔗
BOJ 2447	별 찍기 - 10	분할 정복 기반의 재귀 패턴 출력	-