안녕하세요, 이번에는 분할정복(Divide and Conquer)에 대하여 정리해보려고 합니다.
동적계획법(Dynamic Programming)도 분할정복으로 문제를 푸는 경우가 많아서,
그보다 먼저 정리를 할까 했는데 냅다 문제를 풀어버렸습니다 ㅎㅎ
따라서 이번엔 많은 문제해결에 적용이 되는 분할정복(Divide and Conquer)에 대해 정리해보겠습니다.
분할정복 (Divide and Conquer) 이란?
분할정복 (Divide and Conquer)이란, 큰 문제를 작은 문제로 분할(Divide)하여 작은 문제부터 해결(Conquer)하는 알고리즘 기법입니다.
◆ 핵심 개념
- 문제를 작은 하위 문제(Subproblem)로 분할(Divide)
- 하위 문제를 재귀적으로 정복(Conquer)
- 하위 문제들의 결과를 합쳐서(Combine) 전체 문제를 해결
◆ 분할정복 알고리즘의 구조
- 분할(Divide):
- 문제를 작고 비슷한 하위 문제로 나누기
- 정복(Conquer):
- 하위 문제를 재귀적으로 해결
- 최소 단위가 되면 더이상 나누지 않고 문제를 직접 해결(기저조건/ (재귀)종료조건)
- 결합(Combine):
- 하위 문제의 결과를 이용해 원래 문제의 정답 구하기
◆ 분할 정복이 쓰이는 이유
| 이유 | 설명 |
| 재귀적 접근 | 큰 문제를 다루기 쉬워짐 |
| 성능 개선 | 일부 문제에서 단순 반복 보다 빠른 시간 복잡도 달성 가능 |
| 병렬처리 가능성 | 각 하위 문제를 동시에 해결할 수 있어 병렬처리에 유리 |
◆ 대표적인 예시
분할정복을 사용하는 대표적인 예시들은 아래와 같이 네 가지 정도로 정리해볼 수 있습니다.
1. 병합 정렬 (Merge Sort)
: 배열을 반으로 나누고 각각 정렬한 뒤 두 개를 병합하는 정렬 방법
- 시간복잡도: O(n log n)
2. 퀵 정렬 (Quick Sort)
: 피벗을 기준으로 왼쪽과 오른쪽으로 나눠서 정렬
- 평균 시간복잡도: O(n log n)
3. 이진 탐색 (Binary Search)
: 정렬된 배열에서 중간값과 비교하면서 문제를 절반으로 줄임
- 시간복잡도: O(log n)
4. Karatsuba 곱셈
: 두 수를 분할하여 곱셈의 연산 횟수를 줄이는 알고리즘
- 시간복잡도: 일반 곱셈 O(n^2) / Karatsuba O(n^1.58)
분할정복에 대한 기본적인 내용은 이렇게 정리해볼 수 있겠습니다.
분할정복 (Divide and Conquer) 시간 복잡도
분할정복의 시간복잡도는 보통 아래와 같은 점화식으로 나타낼 수 있습니다.
T(n) = a * T(n/b) + f(n)
| 항목 | 의미 |
| n | 전체 문제 크기 |
| a | 하위 문제의 개수 |
| n/b | 각 하위 문제의 크기 |
| f(n) | 분할/합치는 데 드는 시간 |
즉, "문제를 a개로 나누고, 각각 크기가 n/b이며, 나눈 다음과 합하는 데에 k(n) 시간이 든다" 는 의미입니다.
◆ 대표적인 예시 알고리즘들의 시간 복잡도
| 알고리즘 | 점화식 | 시간복잡도 |
| 병합정렬 | T(n) = 2T(n/2) + O(n) | O(n log n) |
| 이진탐색 | T(n) = T(n/2) + O(1) | O(log n) |
| Karatsuba | T(n) = 3T(n/2) + O(n) | O(n^1.58) |
◆ 마스터 정리(Master Theorem)
위 점화식을 한 번에 계산해주는 게 바로 '마스터 정리'인데요,
T(n) = a * T(n/b) + f(n)
이 때, 점화식의 각 항에 대한 설명은 아래와 같습니다.
a ≥ 1, b > 1, f(n)은 n에 대한 함수
마스터 정리의 3가지 경우는 아래와 같습니다.
| 경우 | 조건 | 시간복잡도 |
| Case 1 | f(n) = O(n^c) where c < 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^c) where c > log_b a,and regularity condition holds | T(n) = Θ(f(n)) |
시간복잡도 분석 - 병합 정렬
점화식: T(n) = 2T(n/2) + O(n)
- a = 2, b = 2, f(n) = Θ(n)
- log_b a = log_2 2 = 1, f(n) = Θ(n^1)
→ Case 2 적용
✔ 결과: T(n) = Θ(n log n)
정리하자면, 시간복잡도는
- 점화식으로 나타내는 것이 핵심
- 마스터 정리를 통해 시간복잡도를 빠르게 계산
- 문제를 얼마나 쪼개고, 합치는 데 시간이 얼마나 드는 지 가 성능을 결정
입니다.
* 마스터 정리에 관한 내용은 추후 포스팅에서 좀 더 다루어 보도록 하겠습니다 !
예제 문제 풀이: BOJ 2630 색종이 만들기
* 예제 문제: BOJ 2630 색종이 만들기
링크: https://www.acmicpc.net/problem/2630
문제
: 흰색 칸과 파란색 칸으로 이루어진 색종이에서, 하얀색만 혹은 파란색만 포함되도록 자를 때의 각 색 종이의 개수를 구하는 문제입니다.
예제
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
먼저 아래와 같이 클래스를 정의해주었습니다.
Colors는 각 흰 종이와 파란 종이의 수량을 저장하기 위한 클래스이고요,
ColorCheck은 현재 탐색하는 색종이의 시작 색깔이 무엇이며, 현재 범위의 색종이가 모두 같은 색인지 여부를 확인하기 위한 클래스입니다.
public static class Colors {
int whiteCnt = 0;
int blueCnt = 0;
}
public static class ColorCheck {
boolean isSameColor = true;
int color = 0;
}
다음은 색종이 색을 검사하는 Method입니다.
startX, startY로 색종이 paper에서 size 범위 내의 색이 모두 같은지 검사합니다.
이 때, 만약 paper의 사이즈가 1이라면 현재 색을 리턴합니다.
사이즈가 1이므로 isSameColor도 true로 리턴합니다.
⬜️
일 때,
isSameColor = true
color = 0
🟦
일 때,
isSameColor = true
color = 1
사이즈가 1이 아니라면 범위 내의 색종이 칸을 전부 검사하여 시작지점과 색이 다르면 isSameColor = false;로 저장해주고 break; 합니다.
🟦⬜️
⬜️🟦
일 때,
isSameColor = false
color = 0 (default 0)
이미 색이 다른 걸 알았으므로 더이상 탐색할 필요가 없습니다.
// 색종이 색 검사
public static ColorCheck colorChecker(int[][] paper, int startX, int startY, int size) {
ColorCheck ans = new ColorCheck();
int nowColor = paper[startX][startY];
if(paper.length == 1) {
ans.isSameColor = true;
ans.color = nowColor;
}
else {
for(int i = startX; i < startX + size; i++) {
for(int j = startY; j < startY + size; j++) {
if(nowColor != paper[i][j]) {
ans.isSameColor = false; // 색이 다른 경우
break;
}
}
if(!ans.isSameColor) {
break; // 색이 이미 다르므로 더이상 탐색할 필요가 x
}
}
if(ans.isSameColor) {
ans.color = nowColor;
}
}
return ans;
}
그리고 색종이 색 확인이 되었으면 분할을 합니다.
색종이 내부 색이 모두 같은 경우는 더 이상 분할하지 않고 색종이 수를 증가시킵니다.
🟦🟦
🟦🟦
일 때,
분할 x, 색종이 수 증가(blueCnt++)
🟦⬜️
⬜️🟦
일 때,
분할 o --> 각 변을 1/2로 줄이면 아래와 같이 네 칸을 각각 재귀적으로 탐색하게 됩니다.
🟦
-> 탐색
⬜️
->탐색
⬜️
-> 탐색
🟦
-> 탐색
색종이 내부 색이 다른 경우는 분할하여 재귀적으로 다시 탐색합니다.
// 색종이 분할
public static Colors dividePaper(int[][] paper, int startX, int startY, int size) {
Colors ans = new Colors();
ColorCheck check = colorChecker(paper, startX, startY, size);
// 분할 시 다음 시작 좌표를 위한 배열
int[] nextX = {startX, startX, startX + size/2, startX + size/2};
int[] nextY = {startY, startY + size/2, startY, startY + size/2};
if(check.isSameColor) { // 같은 색일 경우
if(check.color == 0) {
ans.whiteCnt++;
} else {
ans.blueCnt++;
}
} else { // 다른 색이 있을 경우 분할
for(int i = 0; i < 4; i++) {
Colors now = dividePaper(paper, nextX[i], nextY[i], size/2); // 분할
ans.whiteCnt += now.whiteCnt;
ans.blueCnt += now.blueCnt;
}
}
return ans;
}
실제 소스 캡쳐는 아래와 같습니다.
이 문제를 풀면서, 포인트는
1. 분할정복
2. 분할된 색종이의 수량을 색 별로 count 하는 것
이라고 생각했습니다.
색이 white, blue 두 가지여서 Color 라는 클래스를 생성하여 따로 탐색이 아닌 한 번에 각 색종이의 수량을 구할 수 있도록 구현해 보았습니다.
분할정복은 처음에 문제를 풀어나갈 땐 엄청 헷갈렸는데요,
개념 이해를 하고 풀기 시작하니 규칙을 찾고 그를 구현하는데 재미가 있어서 좋아하는 문제 풀이 유형이 되었습니다 :)
공부하시는 분들도 재귀의 개념과 문제를 작은 단위로 분할하여 해결하는 방식이 익숙해지시면 금방 쉽게 푸실 수 있으실 거예요!
하나씩 알고리즘을 같이 정복해보아요!ㅎㅎ
화이팅입니다 !!
