쉽게 쉽게

[알고리즘] 분할정복(Divide & Conquer)이란? (백준 2630 , 1992, 1780, 1629 ,10830) 본문

알고리즘

[알고리즘] 분할정복(Divide & Conquer)이란? (백준 2630 , 1992, 1780, 1629 ,10830)

곱마2 2026. 4. 15. 20:17
반응형
📌 핵심 요약
  • 분할정복 3단계 — Divide(분할) → Conquer(정복) → Combine(합치기), 기저 조건이 반드시 존재해야 한다
  • 분할정복 거듭제곱 — b가 짝수면 절반으로 쪼개고, 홀수면 하나 떼어내서 O(log b)에 계산한다
  • 행렬 거듭제곱 — 숫자 거듭제곱과 동일한 분할정복 구조, 곱셈만 행렬 곱셈으로 교체하면 된다

1 분할정복(Divide & Conquer)이란?

분할정복은 복잡한 문제를 더 작은 동일한 구조의 하위 문제로 쪼개서 해결하는 알고리즘 설계 기법이다. 재귀(Recursion)를 기반으로 동작하며, 세 단계로 구성된다.

단계 이름 설명
1 Divide (분할) 문제를 더 작은 동일 구조의 하위 문제로 나눈다
2 Conquer (정복) 하위 문제를 재귀적으로 푼다. 더 이상 나눌 수 없으면(기저 조건) 직접 답을 반환한다
3 Combine (합치기) 하위 문제의 결과를 모아 원래 문제의 답을 만든다
ℹ️
기저 조건(Base Case)이란?
재귀 호출을 멈추는 조건이다. 예를 들어 1×1 격자, 지수가 1인 경우처럼 더 이상 쪼갤 수 없는 최소 단위에서 바로 답을 반환한다. 기저 조건이 없으면 무한 재귀로 스택 오버플로우가 발생한다.

분할정복 코드 패턴

분할정복 코드는 항상 아래 구조를 따른다.

 
Java — 분할정복 기본 패턴
void solve(int problem) {
    // 1단계: 기저 조건 — 더 이상 쪼갤 수 없는 최소 단위
    if (isSolvable(problem)) {
        directSolve(problem);
        return;
    }
    // 2단계: Divide — 문제를 작은 단위로 분할
    int[] subProblems = divide(problem);
    // 3단계: Conquer — 재귀 호출로 각각 해결
    for (int sub : subProblems) solve(sub);
    // 4단계: Combine — 결과 합치기
    combine(subProblems);
}

분할정복 거듭제곱 호출 트리

A^10을 예시로 보면, b가 짝수면 절반으로 쪼개고 홀수면 하나 떼어내어 재귀 호출 횟수를 O(log b)로 줄인다.

 
분할정복 거듭제곱 — 호출 트리
matPow(A, 10)  ← 짝수: 절반으로 쪼갬
└─▶ matPow(A, 5)   ← 홀수: 하나 떼어냄
    ├─▶ matPow(A, 4)   ← 짝수: 절반으로 쪼갬
    │   └─▶ matPow(A, 2)
    │       └─▶ matPow(A, 1)  ← 기저 조건: A 반환
    │           반환: A
    │       반환: A × A = A²
    │   반환: A² × A² = A⁴
    └─▶ × A  ← 홀수라 떼어낸 항
    반환: A⁴ × A = A⁵
반환: A⁵ × A⁵ = A¹⁰  ✅
방법 A^10 계산 곱셈 횟수 A^100억 계산
단순 반복 A×A×…×A 9번 100억 번
분할정복 A¹→A²→A⁴→A⁵→A¹⁰ 4번 약 37번

2 분할정복 문제 풀이

분할정복의 전형적인 백준 문제들을 풀이한다. 쿼드트리(4분할), 구구단(9분할), 거듭제곱(지수 분할), 행렬 거듭제곱 유형을 모두 다룬다.

BOJ #2630
색종이 만들기
N ≤ 128 · 시간제한 1초
난이도: Silver II

N×N 격자에서 모든 칸이 같은 색이면 그 색 종이 1장으로 카운트하고, 다르면 4등분해서 재귀적으로 반복한다. 흰 종이와 파란 종이의 수를 출력한다.

풀이 과정
  1. 구역 내 모든 칸을 순회해 첫 번째 칸의 색과 비교한다. 다른 색 발견 즉시 break outer로 이중 루프 탈출
  2. 전부 같은 색이면 해당 색 카운트 +1 후 return
  3. 다르면 size/2로 4등분 — 좌상 → 우상 → 좌하 → 우하 순서로 재귀 호출
 
Java — BOJ 2630
import java.io.*;
import java.util.*;

public class Main {
    static int white = 0, blue = 0;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        check(0, 0, n);
        System.out.println(white);
        System.out.println(blue);
    }

    static void check(int row, int col, int size) {
        boolean all = true;
        int first = arr[row][col];
        outer:
        for (int i = row; i < row + size; i++){
            for (int j = col; j < col + size; j++)
                if (arr[i][j] != first) { 
                	all = false; 
                	break outer; 
                }
		}
        if (all) { if (first == 1) blue++; else white++; return; }

        int h = size / 2;
        check(row,     col,     h); // 좌상
        check(row,     col + h, h); // 우상
        check(row + h, col,     h); // 좌하
        check(row + h, col + h, h); // 우하
    }
}
⚠️
4분할 순서 주의
재귀 호출 순서는 반드시 좌상 → 우상 → 좌하 → 우하여야 한다. row+half는 아래쪽 이동이므로 두 번째에 오면 좌하가 되어버린다.
BOJ #1992
쿼드트리
N ≤ 64 · 시간제한 2초
난이도: Silver I

2630과 동일한 4분할 구조지만, 결과를 숫자 카운트가 아니라 쿼드트리 형식의 문자열로 출력한다. 4분할이 발생할 때마다 괄호로 감싼다.

2630과의 차이점
  1. 입력이 "0001"처럼 공백 없이 붙어있어 line.charAt(j) - '0'으로 파싱해야 한다
  2. 4분할 진입 전 sb.append('('), 완료 후 sb.append(')')로 괄호를 감싼다
  3. 전부 같은 색이면 sb.append(0) 또는 sb.append(1)로 바로 추가하고 return
 
Java — BOJ 1992 핵심 부분
static void check(int row, int col, int size) {
    boolean all = true;
    int first = arr[row][col];
    outer:
    for (int i = row; i < row + size; i++)
        for (int j = col; j < col + size; j++)
            if (arr[i][j] != first) { all = false; break outer; }

    if (all) { sb.append(first); return; }

    int h = size / 2;
    sb.append('(');
    check(row,     col,     h);
    check(row,     col + h, h);
    check(row + h, col,     h);
    check(row + h, col + h, h);
    sb.append(')');
}
BOJ #1780
종이의 개수
N ≤ 3⁷ · 시간제한 2초
난이도: Silver II

2630의 9분할 버전. -1, 0, 1 세 가지 값이 있고, 모두 같으면 해당 카운트 +1, 다르면 3×3으로 9등분해서 재귀 호출한다.

2630과의 차이점
  1. 입력에 -1이 있어 charAt이 아닌 StringTokenizer로 파싱해야 한다
  2. 4분할이 아닌 9분할 — size/3으로 나누고 이중 for문으로 9개 구역 재귀 호출
  3. 카운트 변수가 zero, one, minus_one 세 가지
 
Java — BOJ 1780 핵심 부분
// 9분할 재귀 호출
int third = size / 3;
for (int di = 0; di < 3; di++)
    for (int dj = 0; dj < 3; dj++)
        check(row + di * third, col + dj * third, third);
BOJ #1629
곱셈
A, B, C ≤ 2,147,483,647 · 시간제한 0.5초
난이도: Silver I

A^B mod C를 구하는 문제. B가 최대 약 21억이라 단순 반복 곱셈은 시간 초과. 지수를 절반씩 쪼개는 분할정복으로 O(log B)에 해결한다.

풀이 과정
  1. A^B = A^(B/2) × A^(B/2) (짝수) / A^B = A^(B/2) × A^(B/2) × A (홀수)
  2. 중간 곱셈 결과가 int 범위를 초과하므로 모든 변수를 long으로 선언
  3. 매 곱셈마다 mod 연산 적용 — (half * half) % mod
 
Java — BOJ 1629
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());
        System.out.println(pow(a, b, c));
    }

    static long pow(long a, long b, long mod) {
        if (b == 1) return a % mod;                    // 기저 조건
        long half = pow(a, b / 2, mod);               // Divide
        long result = (half * half) % mod;              // Combine
        if (b % 2 == 1) result = (result * a) % mod;  // 홀수 처리
        return result;
    }
}
💡
long을 써야 하는 이유
A와 C가 최대 2,147,483,647(int 최대값)이므로 A × A는 약 4.6 × 10¹⁸이 될 수 있다. int 범위를 훨씬 초과하므로 반드시 long을 사용해야 한다.
BOJ #10830
행렬 제곱
N ≤ 5 · B ≤ 100,000,000,000 · 시간제한 1초
난이도: Gold IV

N×N 정사각행렬 A와 지수 B가 주어졌을 때 A^B mod 1000 을 구하는 문제. B가 최대 1,000억이라 행렬을 직접 B번 곱하는 건 불가능하고, 1629번과 동일한 분할정복 구조를 행렬에 적용한다.

풀이 과정
  1. 행렬 곱셈 함수 multiply() 구현 — 3중 for문으로 C[i][j] 계산, 매 원소마다 % MOD 적용
  2. 분할정복 matPow(): b가 짝수면 half×half, 홀수면 prev×A — 재귀로 b를 절반씩 줄여나감
  3. 입력할 때부터 % MOD 적용, B는 최대 1,000억이므로 반드시 long으로 선언
 
Java — BOJ 10830
import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static final long MOD = 1000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        long b = Long.parseLong(st.nextToken()); // 최대 1,000억 → long!

        // 1단계: 행렬 입력 (입력부터 % MOD)
        long[][] arr = new long[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++)
                arr[i][j] = Long.parseLong(st.nextToken()) % MOD;
        }

        // 2단계: 분할정복으로 A^B 계산
        long[][] result = matPow(arr, b);

        // 3단계: 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(result[i][j] % MOD);
                if (j < n - 1) sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    // 분할정복 행렬 거듭제곱
    static long[][] matPow(long[][] arr, long b) {
        if (b == 1) return arr;
        if (b % 2 == 0) {
            long[][] half = matPow(arr, b / 2);
            return multiply(half, half);
        } else {
            long[][] prev = matPow(arr, b - 1);
            return multiply(prev, arr);
        }
    }

    // 행렬 곱셈
    static long[][] multiply(long[][] X, long[][] Y) {
        long[][] C = new long[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                for (int t = 0; t < n; t++)
                    C[i][j] += X[i][t] * Y[t][j];
                C[i][j] %= MOD;
            }
        return C;
    }
}

3 유형별 정리

문제 분할 방식 기저 조건 핵심 포인트
2630 색종이 4분할 (size/2) 전부 같은 색 white/blue 카운트
1992 쿼드트리 4분할 (size/2) 전부 같은 색 괄호 ( ) 감싸기
1780 종이의 개수 9분할 (size/3) 전부 같은 값 -1/0/1 세 카운트
1629 곱셈 지수 절반 (b/2) b == 1 long 필수, 홀수 처리
10830 행렬 제곱 지수 절반 (b/2) b == 1 multiply() 함수 분리, B는 long
💡
공통 실수 패턴
① 4분할 순서 오류 (좌상→우상→좌하→우하 순서 지킬 것) ② static 메서드에서 지역변수 배열 접근 불가 (클래스 필드로 선언) ③ 입력 파싱 방식 혼동 (공백 구분은 StringTokenizer, 붙어있으면 charAt) ④ 지수가 클 때 long 미사용 (int 최대값 약 21억 초과 주의)
잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.

 

반응형
저작자표시 (새창열림)