[ALGORITHM - ALGORITHM STUDY] 분할 정복 (Divide and Conquer)

분할 정복은 말 그대로 문제를 두 단계, ①분할과 ②정복으로 나눠서 해결하는 것을 말합니다.

분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데,

문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 겁니다.

또한 문제의 크기가 엄청나게 줄어든다면(N=1 또는 N=2 정도) 그야말로 바로 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀 때의 기저 사례(base case)와 같습니다.

그렇습니다. 대체로 분할 정복은 재귀 호출과 아주 죽이 잘 맞습니다.

그리고 기저 사례들로 각 문제의 답을 풀고, 그 문제들을 불렀던 조금 더 큰 문제는 이 답들을 통해 비교적 간단한 연산처리만 해주면 자신의 답도 구할 수 있습니다.

이런 식으로 첫 문제까지 쌓아올려가며 답을 풀어내는 것이 최종 목적.

[출처] 분할 정복(Divide and Conquer) (수정: 2016-12-25)|작성자 라이

아주 대표적인 예가 병합 정렬(merge sort), 이분 탐색(binary search), 거듭제곱 연산(a^b) 등 입니다.

...

[출처] 분할 정복(Divide and Conquer) (수정: 2016-12-25)|작성자 라이

이제 병합 정렬의 경우를 예로 들어서 얼마나 시간이 단축되는지 설명해보겠습니다.

분할 정복 알고리즘의 수행시간은 문제마다 다 다른데, 여기서 필요한 것은 분할할 때 ①나누어지는 문제의 개수, ②분할 후 문제의 크기, ③각 문제마다 병합(정복) 단계에서 걸리는 시간이 결정하기 때문입니다.

병합 정렬의 경우, 분할할 해당 문제 크기를 N이라 할 때 ①2, ②N/2, ③O(N)입니다. 일단 ①, ②번은 위 그림의 상황과 일치하고, ③ 정보를 통해 최종 시간복잡도를 구할 수 있습니다. (③번이 왜 O(N)인지는 여기서는 설명하지 않겠습니다. 병합 정렬에 대해 찾아보시길.)

분할을 다 했으니 이제 역순으로 저걸 병합해 나갈 차례인데, 아까 살펴본 것처럼 각 단계의 부분문제의 개수가 있습니다.

k-1단계에서는 2^(k-1)번, ... 2단계에서는 2^2=4번, 1단계에서는 2번, 0단계에서는 1번의 병합을 해야 하는데 각 병합에 걸리는 시간이 해당 문제 크기가 N일 때 O(N)이라 했죠.

그러므로 각 단계별로 드는 연산 횟수를 죽 늘어놓았을 때

0단계: 1 * O(N)

1단계: 2 * O(N/2)

2단계: 4 * O(N/4)

...

m단계: 2^m * O(N/(2^m)) = O(N)

...

따라서 단계별 식을 일반화해 보면 각 단계에서 드는 총합 연산량은 O(N)입니다. 이는 매 단계마다 각 문제의 크기 역시 지수적으로 줄어들기 때문이죠!

그리고 아까 봤듯이 단계는 총 O(logN)개 있으므로, 이를 곱해서 O(NlogN)이라는 시간복잡도를 구할 수 있습니다!

버블 정렬, 선택 정렬 등의 기본적인 알고리즘이 O(N^2)이라는 점에서 보면 굉장한 발전이라고 할 수 있으며, 현재 일반적인 알고리즘 중 가장 빠른 퀵 정렬 또한 분할 정복 기법을 사용합니다.

C++의 STL에 속한 sort 함수, C의 qsort 함수 등 여러 언어의 라이브러리에서 이 빠른 분할 정복을 베이스로 한 정렬 함수를 지원합니다.

...

이분 탐색이 간단한 예인데, N개의 정렬되어 있는 수들 중 어떤 값 K의 위치를 찾아내거나, 없다는 것을 판정하는 탐색입니다.

그냥 차례대로 훑어보면 O(N)이지만, 정말 놀랍게도 이분 탐색은 O(logN)의 시간복잡도를 자랑합니다.

[출처] 분할 정복(Divide and Conquer) (수정: 2016-12-25)|작성자 라이

[d출처] 분할 정복(Divide and Conquer) (수정: 2016-12-25)|작성자 라이

출처 : http://blog.naver.com/PostList.nhn?from=postList&blogId=kks227&categoryNo=299&parentCategoryNo=299¤tPage=40

1725 히스토그램 : https://www.acmicpc.net/problem/1725

이문제는 원래 분할정복으로 풀려고 했던 문제이나.. 분할정복으로 실패하고 stack으로 돌렸다.

분할정복으로는

중간값을 찾은 후 Front와 Back 변수를 둔 후에 기둥 중 큰 기둥쪽으로 발을 뻗쳐나가면 되는것이다.

같으면 두 발다 뻗치면 된다.

그렇게 끝까지 찾으면 찾아진다고 한다.

stack의 원리는 간단하다. 나보다 작은 것들은 stack안에서 나보다 아래에 있다.

1. stack의 top보다 크거나 같은 기둥이 보이면 push

2. stack의 top보다 작은 기둥이 보이면 pop!!! 언제까지? stack의 top이 그 기둥보다 작거나 같을 때까지!

3. pop하면서 밑변과 높이를 계산해서 곱해주면된다.

아주 큰 실수를 코드짜는데해서 무려 3시간이 넘게 걸렸다.

내 실수는 index에서 빼는 것이 아니라 pop하면서의 개수를 셌다는 것이다.

예를 들어보자

2 3 4 3 3 의 기둥이 있다.

stack에는 2 3 4가 들어갔다가 3을 만나자마자 4가 나온다.

그리고 나는 4가 1개 나왔으므로 4*1을 width와 비교한다.

이후 stack에는 2 3 3 3의 값이 들어있다.

그렇다면 여기서 나의 넓이의 정답은 9가 나오는 것이다.

이것은 치명적인 실수이다.

index를 건들여야 할것을..그러면 훨씬더 간단한 코드가 나올 것을..

원리를 이해하고 받아들이는 데 이렇게 오랜 시간이 걸린다니..힘들다 8_8

아무튼 수정을 해서 나온 코드는 아래와 같다.

#include <iostream> #include <stack> #include <fstream> #include <algorithm> using namespace std; int main() { stack<long long int> width, height; long long int answer = 0; int histogram_count = 0; long long int temp, index = 0; width.push(0); height.push(0); cin >> histogram_count; if (histogram_count == 0) { cout << 0 << endl; return 0; } while (index != histogram_count) { index++; cin >> temp; while (height.top() > temp) { width.pop(); answer = max(answer, height.top()*(index - width.top() - 1)); height.pop(); } width.push(index); height.push(temp); } while (width.top() != 0) { width.pop(); answer = max(answer, height.top()*(index - width.top())); height.pop(); } cout << answer << endl; }