Divide & Conquer
Divide & Conquer은 분할 정복을 뜻합니다. 분할 정복은 큰 문제를 작은 문제로 분할하여 푼다는 관점에서 DP와 유사합니다. 하지만 DP에서 나타나는 특징인 overlapping subproblem이 나타나지 않습니다. 분할 정복은 크게 아래에 있는 세 가지 단계로 나눌 수 있습니다.
- 문제를 작게 분할하는 단계
- 문제를 푸는 단계
- 푼 문제를 합치는 단계
분할 정복 문제들은 일반적으로 난이도의 편차가 크고, 주로 쉬운 알고리즘 문제로 출제되거나 다른 알고리즘과 섞여서 출제된다고 합니다.
분할 정복을 사용하는 예시
- Binary Search
- Merge Sort
Binary Search
Binary Search는 이분 탐색을 뜻합니다. 이분 탐색은 정렬된 배열에서 특정 원소를 찾을 때 사용됩니다.(정렬된 배열이라는 점이 중요합니다!) 이분 탐색은 𝑂(log 𝑁)의 시간 복잡도를 가집니다.
Binary Search Flow
-
배열을 정렬(정렬되어 있지 않은 경우)
-
양 끝 점을 기준으로 정함
-
두 개의 기준점을 이용해 중앙값을 구함
-
중앙값을 탐색하고자 하는 값과 비교
4-1. 탐색하고자 하는 값보다 중앙값이 크다면 중앙값보다 크거나 같은 모든 값은 탐색을 할 필요X
4-2.탐색하고자 하는 값보다 중앙값이 작다면 중앙값보다 작거나 같은 모든 값은 탐색할 필요X
-
탐색할 필요가 없는 범위를 제거하고 다시 끝 기준점을 정함
-
값을 찾을 떄까지 3~5번 반복
#include <bits/stdc++.h>
using namespace std;
int arr[15] = { 1, 3, 4, 6, 7, 8, 10, 12 ,15, 17, 19, 20, 21, 23, 24 };
int binarySearch(int seq[], int num) {
int l = 0;
int r = sizeof arr / sizeof arr[0];
while (l <= r) {
int mid = (l + r) / 2;
if (num == seq[mid])
return mid;
if (num < seq[mid])
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
int main() {
int n;
scanf_s("%d", &n);
int result = binarySearch(arr, n);
printf("%d", result);
return 0;
}+) binary_search(vector.begin(), vector.end(), searchNum) -> 이분 탐색을 통해 vector내에 searchNum이 존재하는지 확인해주는 함수입니다.
+) 숫자가 정렬되어 있을 경우 lower_bound와 upper_bound를 이용하여 찾고자 하는 값의 갯수를 셀 수 있습니다.(lower_bound는 찾는 값보다 크거나 같은 것중 가장 작은 값(index), upper_bound는 찾는 값보다 큰 값 중 가장 작은 값(index)을 찾기 때문!)
upper_bound(vector.begin(), vector.end(), searchNum) - lower_bound(vector.begin(), vector.end(), searchNum)분할 정복 예제(백준 1629번)
나머지 정리와 분할 정복을 함께 사용해서 풀 수 있는 문제입니다. a의 n승을 봤을 때, n%2 = 0일 경우 a의 n/2승 2개를 곱해줬다고 볼 수 있습니다. 또한 n%2 = 1일 경우는, a에 a의 n-1승을 곱한 수로 볼 수 있습니다. 이렇게 a의 n승을 a의 n/2승 또는 a의 n-1승의 소문제로 만들어서 풀면 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pow(ll a, ll b, ll c) {
if (b <= 0)
return 1 % c;
if (b == 1)
return a % c;
if (b % 2)
return ((a % c) * pow(a, b - 1, c) % c) % c; // 나머지 정리 이용
else {
ll res = pow(a, b / 2, c) % c;
return res * res % c; // 나머지 정리 이용
}
}
int main() {
ll a, b, c;
scanf_s("%lld %lld %lld", &a, &b, &c);
printf("%lld", pow(a, b, c));
return 0;
}Merge Sort
Merge sort는 정렬의 한 방법으로 분할 정복 기법을 사용하여 주어진 배열을 정렬하는 방법입니다. Merge sort는 아래와 같은 과정으로 배열을 정렬합니다.
Merge Sort Flow
-
주어진 배열이 충분히 작은 상태이거나 비교 가능한 상태가 될 때까지 반으로 나눔(divide)
-
나뉘어진 배열을 비교, 이때 두 배열은 단위 배열이거나 정렬된 상태의 배열이므로 가장 앞의 원소를 비교하며 새로운 배열에 정렬된 상태로 배치(conquer)
#include <bits/stdc++.h>
using namespace std;
void merge(vector<int>& seq, int l, int r) {
vector<int> tmp;
int mid = (l + r) / 2;
int f = l, s = mid + 1;
while (f <= mid && s <= r) {
if (seq[f] <= seq[s])
tmp.push_back(seq[f++]);
else
tmp.push_back(seq[s++]);
}
for (; f <= mid; ++f)
tmp.push_back(seq[f]);
for (; s <= r; ++s)
tmp.push_back(seq[s]);
for (int i = l; i <= r; ++i)
seq[i] = tmp[i - l];
}
void MergeSort(vector<int>& seq, int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
MergeSort(seq, l, mid);
MergeSort(seq, mid + 1, r);
merge(seq, l, r);
}
}
int main() {
srand(time(0));
int n; scanf_s("%d", &n);
vector<int> seq(n);
for (int i = 0; i < n; ++i)
seq[i] = rand() % 100 + 1;
MergeSort(seq, 0, n - 1);
for (auto i : seq)
printf("%d ", i);
}Decision Problem
Decision problem은 결정 문제라는 뜻입니다. 어떤 조건이 주어지고 '조건에 맞는 값을 구하라' 등의 문제를 '어떤 값 A가 주어졌을 때 이 값은 조건에 맞는가' 식의 결정 문제로 바꿔서 해결할 수 있습니다. 또한 이때 A를 고르고 조건에 맞은 뒤 또 더 조건에 가까운 다른 A를 구하는 과정에서 Binary search를 사용하면 매우 빠르게 문제를 해결할 수 있습니다.
Decision Problem Flow
- 어떤 문제가 주어진 조건 Z에 의해 답 A가 결정된다고 가정
- 답의 범위를 결정(binary search)
- 범위의 중간값과 조건 Z를 확인
- 조건 Z에 의해 범위의 절반을 버림
- 해당 과정 반복
Decision Problem 예제(백준 1939번)
해당 문제는 주어진 값들을 양방향 그래프 형식으로 저장한 뒤, BFS와 binary search를 이용한 decision problem 방식으로 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct EDGE {
int to, w;
};
int n, m, s, f;
vector<EDGE> graph[10001];
bool chk(int num) { // BFS사용
int check[10001] = { 0 };
queue<EDGE> q;
q.push({ s, (int)1e9 });
check[s] = 1;
while (q.size()) {
int frontTo = q.front().to;
int frontW = q.front().w;
q.pop();
if (frontTo == f && frontW >= num)
return 1;
for (int i = 0; i < graph[frontTo].size(); i++) {
int nt = graph[frontTo][i].to;
int nw = graph[frontTo][i].w;
if (!check[nt] && nw >= num) {
check[nt] = 1;
q.push({ nt, nw });
}
}
}
return 0;
}
int main() {
scanf_s("%d %d", &n, &m);
int l = 1e9;
int r = 0;
for (int i = 0; i < m; i++) {
int from, to, w;
scanf_s("%d %d %d", &from, &to, &w);
graph[from].push_back({ to, w });
graph[to].push_back({ from, w });
l = min(l, w);
r = max(r, w);
}
scanf_s("%d %d", &s, &f);
int ans = 0;
while (l <= r) { // Binary search를 이용한 decision problem 방식
int mid = (l + r) / 2;
if (chk(mid)) {
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
printf("%d", ans);
return 0;
}