티스토리 뷰

Algorithm/알고리즘 공부 일기

분할 정복(Divide and Conquer) - 개념부터 백준 문제까지

poopooreum 2026. 4. 6. 15:43
반응형

✏️ 분할 정복(Divide and Conquer)이란?

분할 정복은 큰 문제를 작은 문제로 나누어 해결하는 알고리즘 설계 패러다임으로 세 단계로 이루어진다.

1. Divide  (분할) : 문제를 더 작은 부분 문제로 나눈다
2. Conquer (정복) : 부분 문제를 재귀적으로 해결한다
3. Combine (결합) : 부분 해를 합쳐 원래 문제의 해를 구성한다

 

✏️ 핵심 아이디어 

 

크기 N인 문제를 크기 N/2인 두 문제로 나눌 수 있다면, 재귀 트리의 높이가 log₂N로 줄어든다. 예를 들어, N=8짜리 문제를 단 3단계(log₂8=3)만에 base case까지 분해하게 되는데 이 구조 덕분에 많은 알고리즘이 O(N) → O(N log N) 혹은 그 이하로 줄어든다

solve(1..8)
├── solve(1..4)
│   ├── solve(1..2)
│   │   ├── solve(1)  ← base case
│   │   └── solve(2)  ← base case
│   └── solve(3..4)
│       ├── solve(3)
│       └── solve(4)
└── solve(5..8)
    └── ...

 

✏️ 시간 복잡도 분석 - 마스터 정리(Master Theorem)

분할 정복 알고리즘의 시간 복잡도는 마스터 정리로 분석하게 된다.

T(n) = a·T(n/b) + f(n)

a : 재귀 호출 횟수 (몇 개로 나누는가)
b : 입력 크기를 줄이는 비율 (얼마나 작게 나누는가)
f(n) : 분할/결합 단계의 비용

 

케이스 조건 결론
Case 1 f(n) = O(n^(log_b a - ε)) T(n) = Θ(n^log_b a)
Case 2 f(n) = Θ(n^(log_b a)) T(n) = Θ(n^log_b a · log n)
Case 3 f(n) = Ω(n^(log_b a + ε)) T(n) = Θ(f(n))

 

✏️ 분할 정복 vs 동적 프로그래밍

두 패러다임은 모두 재귀적 구조를 사용하지만, 결정적인 차이가 있다.
부분 문제가 서로 독립적이면 분할 정복, 겹친다면 DP를 선택하면 된다/

피보나치를 예로 들면:

  • 단순 재귀: O(2ⁿ) — 같은 값을 중복 계산
  • DP: O(n) — 메모이제이션으로 중복 제거
  • 행렬 거듭제곱(분할 정복): O(log n) — 완전히 다른 접근
구분 분할 정복 동적 프로그래밍
부분 문제 중복 없음 (독립적) 있음 (겹침)
메모이제이션 불필요 필수
접근 방향 Top-down 재귀 Top-down 또는 Bottom-up
대표 예시 병합 정렬, 빠른 거듭제곱, 쿼드트리 피보나치(naive), LCS, 배낭 문제

 

✏️ 문제 목록

문제 번호 제목 핵심 개념
1 2630 색종이 만들기 쿼드트리 (4분할 재귀)
2 1992 쿼드트리 쿼드트리 문자열 조합
3 1780 종이의 개수 9분할 재귀
4 1629 곱셈 빠른 거듭제곱 O(log n)
5 11401 이항 계수 3 페르마의 소정리 + 모듈러 역원
6 2740 행렬 곱셈 행렬 곱 O(N³)
7 10830 행렬 제곱 행렬 거듭제곱 O(N³ log n)
8 11444 피보나치 수 6 행렬 거듭제곱 응용
9 6549 히스토그램에서 가장 큰 직사각형 분할 정복 최적화

1️⃣ BOJ 2630 - 색종이 만들기

문제 링크

#include <iostream>
using namespace std;

int arr[129][129];
int whiteCount = 0, blueCount = 0;

void solve(int x, int y, int size)
{
    int color = arr[x][y];
    bool same = true;

    // 현재 영역이 모두 같은 색인지 검사
    for (int i = x; i < x + size; i++)
    {
        for (int j = y; j < y + size; j++)
        {
            if (arr[i][j] != color)
            {
                same = false;
                break;
            }
        }
        if (!same)
            break;
    }

    // 모두 같은 색이면 개수 증가
    if (same)
    {
        if (color == 0)
            whiteCount++;
        else
            blueCount++;
        return;
    }

    // 섞여 있으면 4등분
    int half = size / 2;
    solve(x, y, half);
    solve(x, y + half, half);
    solve(x + half, y, half);
    solve(x + half, y + half, half);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> arr[i][j];
        }
    }

    solve(1, 1, N);

    cout << whiteCount << "\n"
         << blueCount;
}

 

2️⃣ BOJ 1992 - 쿼드트리

문제 링크

#include <iostream>
using namespace std;

char arr[65][65];
void solve(int x, int y, int size)
{
    char temp = arr[x][y];
    bool isSame = true;

    // 같은지 탐색
    for (int i = x; i < x + size; i++)
    {
        for (int j = y; j < y + size; j++)
        {
            if (temp != arr[i][j])
            {
                isSame = false;
                break;
            }
        }
        if (!isSame)
            break;
    }

    // 같은 경우
    if (isSame)
    {
        cout << temp;
        return;
    }

    int half = size / 2;
    cout << "(";
    solve(x, y, half);
    solve(x, y + half, half);
    solve(x + half, y, half);
    solve(x + half, y + half, half);
    cout << ")";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            cin >> arr[i][j];
    }

    solve(1, 1, N);
}

3️⃣ BOJ 1780 — 종이의 개수

문제 링크

#include <iostream>
using namespace std;

int arr[3000][3000];
int minusCount, zeroCount, plusCount;
void solve(int x, int y, int size)
{
    int temp = arr[x][y];
    bool isSame = true;

    // 같은지 탐색
    for (int i = x; i < x + size; i++)
    {
        for (int j = y; j < y + size; j++)
        {
            if (temp != arr[i][j])
            {
                isSame = false;
                break;
            }
        }
        if (!isSame)
            break;
    }

    // 같은 경우
    if (isSame)
    {
        if (temp == -1)
            minusCount++;
        else if (temp == 0)
            zeroCount++;
        else
            plusCount++;
        return;
    }

    int half = size / 3;
    solve(x, y, half);                       // 좌상단
    solve(x + half, y, half);                // 가운데 위
    solve(x + half * 2, y, half);            // 우상단
    solve(x, y + half, half);                // 좌중
    solve(x + half, y + half, half);         // 정가운데
    solve(x + half * 2, y + half, half);     // 우중
    solve(x, y + half * 2, half);            // 좌하단
    solve(x + half, y + half * 2, half);     // 가운데 아래
    solve(x + half * 2, y + half * 2, half); // 우하단
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            cin >> arr[i][j];
    }

    solve(1, 1, N);
    cout << minusCount << "\n"
         << zeroCount << "\n"
         << plusCount;
}

4️⃣ BOJ 1629 — 곱셈

문제 링크

#include <iostream>
using namespace std;

long long a, b, c;
long long solve(long long n)
{
    if (n == 1)
        return a % c;
    long long temp = solve(n / 2);

    if (n % 2 == 0)
        return (temp * temp) % c;
    else
        return ((temp * temp) % c * a) % c;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b >> c;
    cout << solve(b);
}

 

5️⃣ BOJ 11401 — 이항 계수 3

문제 링크

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long power(long long a, long long m)
{
    if (m == 0)
        return 1;

    long long temp = power(a, m / 2);
    temp = temp * temp % MOD;

    if (m % 2 == 1)
        temp = temp * a % MOD;
    return temp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    k = min(k, n - k);

    long long A = 1, B = 1;
    for (int i = 0; i < k; i++)
    {
        A = A * (n - i) % MOD;
        B = B * (i + 1) % MOD;
    }

    cout << A * power(B, MOD - 2) % MOD << '\n';
}

6️⃣ BOJ 2740 — 행렬 곱셈

문제 링크

#include <bits/stdc++.h>
using namespace std;

int matrix1[101][101];
int matrix2[101][101];
int matrixMul[101][101];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> matrix1[i][j];
        }
    }

    cin >> m >> k;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < k; j++)
        {
            cin >> matrix2[i][j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int c = 0; c < k; c++)
            {
                matrixMul[i][c] += matrix1[i][j] * matrix2[j][c];
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            cout << matrixMul[i][j] << " ";
        }
        cout << '\n';
    }
}

 

7️⃣ BOJ 10830 — 행렬 제곱

문제 링크

#include <iostream>
#include <vector>

using namespace std;
typedef vector<vector<long long>> Matrix;
int n;
// 행렬 곱셈
Matrix multiply(const Matrix &A, const Matrix &B)
{
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < n; k++)
        {
            for (int j = 0; j < n; j++)
            {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= 1000;
            }
        }
    }
    return C;
}
// 분할 정복
Matrix power(Matrix A, long long b)
{
    // 더 이상 나눌 수 없음
    if (b == 1)
        return A;

    // 절반을 구하고, 절반끼리 곱셈을 함
    Matrix half = power(A, b / 2);
    Matrix result = multiply(half, half);

    // 홀수인 경우에는 해당 매트릭스를 한 번더 곱함
    if (b % 2 == 1)
        result = multiply(result, A);
    return result;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long b;
    cin >> n >> b;

    // 2차원 행렬 입력 및 선언
    Matrix A(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> A[i][j];
            A[i][j] %= 1000;
        }
    }

    Matrix result = power(A, b);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << result[i][j];
            if (j < n - 1)
                cout << ' ';
        }
        cout << '\n';
    }
}

 

8️⃣ BOJ 11444 — 피보나치 수 6

문제 링크

    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef vector<vector<ll>> Matrix;
    const ll MOD = 1e9 + 7;

    Matrix multiply(const Matrix &A, const Matrix &B)
    {
        int n = A.size();
        Matrix C(n, vector<ll>(n, 0));
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++)
                for (int j = 0; j < n; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    }

    Matrix power(Matrix A, ll b)
    {
        if (b == 1)
            return A;

        Matrix half = power(A, b / 2);
        Matrix result = multiply(half, half);

        if (b % 2 == 1)
            result = multiply(result, A);

        return result;
    }

    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        ll n;
        cin >> n;

        if (n == 0)
        {
            cout << 0;
            return 0;
        }
        if (n == 1)
        {
            cout << 1;
            return 0;
        }

        Matrix A = {{1, 1}, {1, 0}};
        Matrix result = power(A, n - 1);

        cout << result[0][0];
    }

 

✏️ 전체 정리

개념  시간 복잡도 관련 문제
쿼드트리 (4분할 재귀) O(N² log N) 2630, 1992
9분할 재귀 O(N² log N) 1780
빠른 거듭제곱 O(log n) 1629, 11401
페르마의 소정리 + 역원 O(N + log p) 11401
행렬 곱셈 O(N³) 2740
행렬 거듭제곱 O(N³ log n) 10830
행렬 거듭제곱 (피보나치) O(log n) 11444
분할 정복 최적화 O(N log N) 6549

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > 알고리즘 공부 일기' 카테고리의 다른 글

이분 탐색(Binary Search) 완전 정복 - 개념부터 백준 문제까지  (0) 2026.04.09
Algorithm 공부 #28 - 확장 유클리드 호제법(Extended Euclidean Algorithm)  (0) 2024.04.27
Algorithm 공부 #27 - KMP(Knuth–morris–pratt)  (2) 2024.04.19
Algorithm 공부 #26 - 이분 매칭(Binary Matching)  (0) 2024.04.14
Algorithm 공부 #25 - 기하학(Geometry)  (3) 2024.03.30
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2026/07   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함