1. 분할 정복법이란?
2. 분할 정복법의 속성
3. 대표적인 분할 정복 알고리즘(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트)
4. 분할 정복 문제 풀이
1. 분할 정복법이란?
분할 정복
:Divide and Conquer
작은 문제로 분할하여 문제를 해결하는 방법
헝가리 출신 미국인 수학자인 폰 노이만이 병합 정렬을 통해 분할 정복을 설명한 것은 1945년이다.
엄청나게 큰 문제를 조금씩 나눠가면서 풀기 용이한 문제로 나눈 다음 다시 합쳐서 해결하자는 개념에서 출발하였다.
2. 분할 정복법의 속성
분할 정복법은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화할 수 있다.
- 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
- 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
이와 같이 문제를 2개 또는 그 이상의 작은 부분 문제로 나누고(분할) 푼 다음(정복) 다시 합쳐서(조합) 정답을 구하는 것이다.
큰 문제를 작은 문제로 나눠서 푼 다음 합친다는 면에서 다이나믹 프로그래밍과 개념이 비슷하다고 생각할 수도 있지만, 다이나믹 프로그래밍과의 차이는 작은 문제가 중복이 되냐 안되냐의 차이다.
- 다이나믹 : 중복이 되므로, 메모리제이션으로 중복을 제거
- 분할정복 : 중복이 되지 않음. 모두 한 번씩 푼다.
분할 정복은 재귀적으로 자신을 호출하기 때문에 재귀 함수(recursive function)를 통해 자연스럽게 구현된다.
function F(x):
if F(x)가 간단 then:
return F(x)를 계산한 값
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값
- 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.
이를 위해서 문제는 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있고 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 된다.
- 함수 호출 오버헤드가 있다.
함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 있고, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 메모리를 과도하게 사용하게 된다는 단점이 있다. 이는 스택, 큐 등의 자료구조를 이용하여 구현할 경우 해결된다.
- 하향식(top-down) 접근 방법이다.
최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다.
3. 대표적인 분할 정복 알고리즘(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트)
대표적인 알고리즘으로는 이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트 등이 있다.
이분 탐색(Binary Search)
정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘이다.
정렬이 되어있어야 되고, 리스트의 크기를 N이라고 했을 때
O(logN)의 시간이 걸린다. : 이유는 크기가 N인 리스트를 계속해서 절반으로 나누기 때문이다.
리스트에서 정렬이 되어 있지 않을때는 일반적인 탐색의 속도는 O(N)이 걸리지만
이분 탐색은 N개가 있을 때 한 개가 나올 될 때까지 계속 2로 나눠서 푼다.
(N, N/2, N/4, N/8, ... , )
이분 탐색.
L = 가장 왼쪽 인덱스
R = 가장 오른쪽 인덱스
M = L+R/2
가운데 값을 비교하며 절반을 없앤다.
고로 정답을 찾는 리스트의 크기가 한 번마다 반이 없어진다.
while(left <= right) {
int mid = (left + right) /2;
if (a[mid] == x) {
position = mid;
break;
} else if (a[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}상한과 하한(Upper & Lower Bound)
상한 :큰 수 중 첫 번째 수
하한 : 크거나 같은 수 중 첫 번째 수
중복이 가능한 리스트에서 어떤 수의 상한(인덱스 번호)에서 하한(인덱스 번호)을 빼면 그 수의 개수와 같다.
이분 탐색을 이용하여 구현 할 수 있다.
/ lower bound
while(left <= right) {
int mid = (left + right) /2;
if (a[mid] == x) { //같으면 찾은 건 똑같다.
position = mid;
right = mid -1; //오른쪽을 왼쪽으로 이동시킴. 하한을 찾기 위해서 같아도 같은것 중에서 첫번 쨰 수를 찾기위해 이동.
} else if (a[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// upper bound
while(left <= right) {
int mid = (left + right) /2;
if (a[mid] == x) {
position = mid+1; // ?? 오답?
right = mid+1; //같으면 오른쪽을 찾기 위해 오른쪽으로 이동.
} else if (a[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
퀵 소트(Quick Sort)
평균적인 상황에서 최고의 성능을 자랑하는 알고리즘
피벗(pivot)을 하나 고른 다음, 그것보다 작은 것을 앞으로 큰 것을 뒤로 보낸다.
그다음, 피벗의 앞과 뒤에서 퀵 정렬을 수행한다.
평균 NlogN
최악의 경우에는 O(N^2)이 걸린다.
최악의 경우 : 피봇이 파티션에서 가장 큰 수 일 경우
피봇을 고르는 방법 : 가장 앞, 가장 뒤, 중간값, 등 여러 가지가 있음.
이미 정렬된 수를 정렬할때 피봇을 가장 앞 또는 가장 뒤에서 선택할 때 N^2 된다..
int choosePivot(int low, int high) {
return low + (high-low)/2; // (low+ high)/2와 같은 의미를 가짐.
}
int partition(int low, int high) {
int pivotIndex = choosePivot(low, high);
int pivotValue = a[pivotIndex];
swap(a[pivotIndex], a[high]);
int storeIndex = low;
for(int i = low; i<high; i++) {
if(a[i] < pivotValue) {
swap(a[i], a[storeIndex]);
storeIndex += 1;
}
}
swap(a[storeIndex], a[high]);
return storeIndex;
}
void quicksort(int low, int high) {
if( low < high) {
int pivot = partition(low, high);
quicksort(low, pivot-1);
quicksort(pivot+1, high);
}
}
퀵 셀렉트(Quick Select)
정렬되지 않는 리스트에서 k번째 작은 수를 찾는 알고리즘
퀵 소트와 같지만, 한 쪽만 호출한다.(찾는 값이 왼쪽인지 오른쪽인지에 따라서)
따라서, 시간복잡도가 O(N)으로 줄어들지만, 최악의 경우에는 O(N^2)이다.
사용할 일은 거의 없다.// 이러한 것이 있다 정도로 생각하자.
int quickselect(int low, int high, int k) {
if pivot = partition(low, high);
if(pivot == k) {
return a[k];
} else if( k < pivot) {
return quickselect(low, pivot-1, k);
} else {
return quickselect(pivot+1, high, k);
}
}
머지 소트 Merge Sort
N개를 정렬하는 알고리즘(시간 복잡도 O(N))
리스트를 가운데서 나눠서 왼쪽 오른쪽으로 나눈다.
반복..
최종적으로 합쳐서 N개를 정렬하는 방법이다.
하나가 될때 까지 나눈다.(가장 작은 문제)
합치면서 정렬된 상태를 만들어 준다.
시간복잡도 : 나누어지는 단계가 몇 단계인지 (logN),
왼쪽 오른쪽 정렬되어 있는배열을 합치는데 걸리는 시간(O(N))
머지 소트에서 배열을 합치는 알고리즘 구현
젤 왼쪽이 작은 것이므로
왼쪽 오른쪽 배열에서 왼쪽을 서로 비교하면서 채워 넣는다.
각 단계에서 합쳐지는 시간(O(N)) * 단계의 개수 (logN) = 전체 시간 (O(NlogN))
void merge(int start, int end) {
int mid = (start + end)/2;
int i = start, j = mid +1, k = 0;
while(i <= mid && j <= end) {
if(a[i] <= a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
}
while(i <= mid) b[k++] = a[i++];
while(j <= end) b[k++] = a[j++];
for(int i= start; i <= end; ++i) {
a[i] = b[i-start];
}
}
void sort(int start, int end) {
if (start == end) {
return;
}
int mid = (start + end)/2;
sort(start, mid);
sort(mid+1, end);
merge(start, end);
}4. 분할 정복 문제 풀이
10815 숫자카드 : https://www.acmicpc.net/problem/10815
이분 탐색을 이용하여 답을 찾는다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
int n, m;
scanf("%d", &n);
vector<int> arr(n);
for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
sort(arr.begin(), arr.end());
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
int num;
scanf("%d", &num);
int left = 0, right = n - 1;
int ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == num) {
ans = 1;
break;
} else if (arr[mid] > num) right = mid - 1;
else left = mid + 1;
}
printf("%d ", ans);
}
}
10816 숫자카드2 : https://www.acmicpc.net/problem/10816
특정카드가 몇개인지 구하는 문제
상한과 하한을 찾아서 그 위치를 빼면 되는 문제.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
int n, m;
scanf("%d", &n);
vector<int> arr1(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &arr1[i]);
}
sort(arr1.begin(), arr1.end());
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
int num, upper=0, lower=0;
scanf("%d", &num);
int left = 0, right = n - 1;
while (left <= right) { //lower bound
int mid = (left + right) / 2;
if (arr1[mid] == num) {
lower = mid;
right = mid - 1;
} else if (arr1[mid] > num) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
left = 0;
right = n - 1;
while (left <= right) { //upper bound
int mid = (left + right) / 2;
if (arr1[mid] == num) {
upper = mid+1;
left = mid +1;
}
else if (arr1[mid] > num) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
printf("%d ", upper - lower);
}
}
1780 종이의 개수 : https://www.acmicpc.net/problem/1780
분할정복의 대표 문제.
모두 같다면 +1
다르다면 종이를 9등분 하여 각각을 호출함.
재귀로 구현
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int arr[3000][3000];
int ans[3];
void a(int y,int x, int size) {
int status = arr[y][x];
int divide = false;
for (int i = y; i < y+size; ++i) for (int j = x; j < x + size; ++j)
if (status != arr[i][j]) {
divide = true;
break;
}
if(divide) {
int k = size / 3;
for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j)
a(y+k*i, x+k*j, k);
}
else
ans[status + 1]++;
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
scanf("%d", &arr[i][j]);
a(0, 0, n);
printf("%d\n%d\n%d", ans[0], ans[1], ans[2]);
}
11729 하노이 탑 이동 순서 : https://www.acmicpc.net/problem/11729
규칙 2가 중요.
n개의 원판을 1에서 3으로 이동시키고 싶다면
1. n-1개의 원판을 1에서 2로 이동시킨다.
2. n번째 원판을 1에서 3으로 이동시킨다.
3. n-1개의 원판을 2에서 3으로 이동시킨다.
n-1개의 원판을 1에서 2로 이동시키고 싶다면
1. n-2개의 원판을 1에서 3으로 이동시킨다.
....
분할정복 문제는 큰 문제만 파악하면 작은 문제도 같은 방식으로 해결 가능하다.
#include <cstdio>
using namespace std;
void f(int n, int start, int end) {
if (n == 1) {
printf("%d %d\n", start, end);
}
else {
int any = 6 - (start + end);
f(n - 1, start, any);
printf("%d %d\n", start, end);
f(n - 1, any, end);
}
}
int main(void) {
int n, ans = 1;
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
ans = 2 * ans + 1;
}
printf("%d\n", ans);
f(n, 1, 3);
}
2263 트리의 순회
프리오더 : 루트, L, R
인오더 : L, 루트, R
포스트오더 : L, R, 루트
포스트오더의 끝이 루트라는 것과
인오더에서 루트 위치를 찾으면 L과 R을 찾을 수 있다는 것을 이용.
O(1)만에 자료를 찾기 위해 position배열을 사용.
(그림) left의 길이와, right의 길이를 설명..
시간복잡도 : O(N)
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int inorder[100001];
int postorder[100001];
int position[100001];
void f(int in_start, int in_end, int post_start, int post_end) {
if (in_start > in_end || post_start > post_end) return;
int root = postorder[post_end];
int index = position[root];
int left = index - in_start;
printf("%d ", root);
f(in_start, index - 1, post_start, post_start + left - 1);
f(index + 1, in_end, post_start + left, post_end - 1);
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &inorder[i]);
for (int i = 0; i < n; ++i) scanf("%d", &postorder[i]);
for (int i = 0; i < n; ++i) position[inorder[i]] = i;
f(0, n - 1, 0, n - 1);
}
1074 Z
종이의 개수와 매우 비슷한 문제
4개로 나누면 되는 문제
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int ans=0;
void f(int y, int x, int size) {
int sum = 0;
if (size == 1) {
cout << ans;
return;
}
if (y >= size / 2) {
sum+=2;
y -= size / 2;
}
if (x >= size / 2) {
sum++;
x -= size / 2;
}
ans += sum * (size*size / 4);
f(y, x, size / 2);
}
int main(void) {
int n, y, x;
cin >> n >> y >> x;
int size = pow(2, n);
f(y, x, size);
}
2447 별찍기-10
종이의 개수와 매우 비슷
9개로 나누어서
가운데는 빈칸, 8개는 같은 모양으로 표현
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
char a[2188][2188];
void f(int y, int x, int n) {
if (n == 3) {
a[y + 1][x + 1] = ' ';
return;
}
for (int h = y + n / 3; h < y + 2 * (n / 3); ++h) {
for (int w = x + n / 3; w < x + 2 * (n / 3); ++w) {
a[h][w] = ' ';
}
}
for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
f(y + i * (n / 3), x + j * (n / 3), n/3);
}
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) a[i][j] = '*';
f(0, 0, n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) printf("%c", a[i][j]);
puts("");
}
}
1517 버블소트
버블 소트를 진행했을 때 스왑이 총 몇 번 발생하는지 출력하는 문제
//버블소트과정 유투브에 치면 정말 버블같다.
버블 소트는 O(N^2)이기 때문에 실제로 버블 소트를 진행하지 않고 스왑이 총 몇 번 발생했는지 알아내야 된다.
버블 소트에서 스왑은 앞에 있는 게 더 커서 뒤로 가는 과정이다.
->앞에 있으면서 더 큰 수의 개수를 세주면 된다.
스왑의 개수 = Inversion : A[i]>A[j](i<j)
이유 : 왼쪽에 큰 수가 있으면 오른쪽에 있는 작은 수와 자리를 바꾸는 과정이 꼭 한번 필요하기 때문에.
왼쪽에 있으면서 더 큰 수가 몇 개인지 구한다.
그림(오른쪽에 있는 게 이동할 때 왼쪽에 있는 것의 개수가 몇 개인지 확인)
머지 소트에서 구현할 수 있다.
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
long long ans = 0;
void merge(int start, int end, vector<int> &a) {
if (start == end) return;
int mid = (start + end) / 2;
int index1 = start, index2 = mid + 1;
vector<int> b(end - start+1);
int size = 0;
while (index1 <= mid && index2 <= end) {
if (a[index1] <= a[index2]) {
b[size++] = a[index1++];
}
else {
b[size++] = a[index2++];
ans += (long long)mid - index1 + 1;
}
}
while (index1 <= mid) b[size++] = a[index1++];
while (index2 <= end) b[size++] = a[index2++];
for (int i = start; i <= end; ++i) a[i] = b[i-start];
}
void divide(int start, int end, vector<int> &a) {
if (start >= end) return;
int mid = (start + end) / 2;
divide(start, mid,a);
divide(mid + 1, end,a);
merge(start, end, a);
}
int main(void) {
int n;
scanf("%d", &n);
vector<int> v(n);
for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
divide(0, n - 1, v);
printf("%lld\n", ans);
}'Algorithm > Intermediate' 카테고리의 다른 글
| 브루트 포스[4]:두포인터, 중간에서 만나기 (Brute Force[4]:Two Pointers, Meet in the Middle(MITM)) (0) | 2021.09.19 |
|---|---|
| 이분탐색 문제 풀이[Binary Seach PS] (0) | 2021.08.24 |
| 그리디 알고리즘(Greedy Algorithm) (0) | 2021.06.12 |
| 너비 우선 탐색(BFS, Breadth First Search) (0) | 2021.06.06 |
| 브루트포스[2] - 재귀 함수 (2) | 2021.04.16 |
