분할 정복(Divide and Conquer)

분할 정복이란? 

주어진 문제에서 길이를 반으로 계속해서 잘라 최소 단위로 만든 뒤 ,

최소단위를 해결함으로써 상위 문제를 계속해서 해결해 결과적으로 정답을 도출해내는 알고리즘이다. 

아래 사진을 보면 해당 문제를

아래로 갈 수록 반으로 분할(빨간색)

위로 갈 수록 하나로 병합(파란색)

split과 merge를 통해 problem을 해결한다. 

 

1

분할 정복을 통한 대표적인 알고리즘으로는 

병합 정렬(merge sort), 이분 탐색(binary search)이 있다.

그중에 우리는 병합 정렬을 통해 분할 정복을 다시 보고자한다. 

 

병합 정렬을 그림으로 보자면 아래와 같다. 

2

일단 숫자열을 계속해서 반으로 나누어 하나의 가장 작은 단위로 만든다.

그 뒤에  서로 다른 두 배열의 앞 인덱스 값을 비교하여 작은 요소를 왼쪽으로 추가하여 새로운 배열로 합병하는 정렬방식이다. 

 

그렇다면 얼마나 이 정렬이 빠를까? 

보통의 경우  버블 정렬, 선택 정렬이 O(n^2)인 경우와 비교하면 병합 정렬은O(NlogN)이다. 

 

어떻게 그렇게 드는가 설명하겠다. 

1번쨰 N개의 문제를 2로 나누면  한 문제에 O(N/2)가 든다.

2번째 N/2개의 문제를 2로 나누면 한 문제에 O(N/4)가 든다.

3번쨰 N/8개의 문제를 2로 나누면 한 문제에 O(N/8)가 든다.

그렇게 반복하다 보면 

m번째 2^m개의 문제를 풀 떄 O(N/(2^m))가 든다. 

이들의 연산량을 총합으로 하면 O(N)이 되는 것이다.

단계는 총O(logN)개가 있으므로 두개를 곱하면 (단계) * (연산량) = O(NlogN)이라는 시간복잡도를 갖게된다

 

그럼 방금배운 분할 정복알고리즘을 기반으로 문제를 풀어 보도록하겠다.

 

6549번: 히스토그램에서 가장 큰 직사각형

해당 문제는 히스토그램 내부에서 그릴 수 있는 가장 큰 직사각형의 넓이를 구하는 문제다. 

직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000)

그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다

벌써 n^2가 100억이다... 그럼 n^2아래 계산해야할 테인데... 우리가 방금 배운게 있지 않은가

 

해당 문제를 분할 정복으로 생각해보자. 

히스토그램을 일단 반으로 나눠서 보고자 한다. 

반을 기준으로 왼쪽에서 가장 큰 넓이를 가진 직사각형 ,반을 기준으로 오른쪽에서 가장 큰 넓이를 가진 직사각형 

이렇게 하면 문제를 풀 수있지 않을까?

결론은 아니다. 

나눠진 선을 포함하는 직사각형 또한 생각해야한다. 

분할선을 포함한 직사각형의 넓이가 가장 큰 직사각형일 수도 있기 때문이다. 

 

# 6549 BOJ
import sys

def divdeandconquer(a):
    if len(a) == 1:
        return a[0]
    if len(a) % 2 == 1: # 홀수일 떄
        a = [0] + a #히스토그램에 0을 하나 넣어준다.
    d = len(a) // 2 #중앙
    x = a[:d] # 중앙에서 좌
    y = a[d:] # 중앙에서 우
    cnt = 2
    tmpmax = min(a[d - 1], a[d]) # 중앙혹은 중앙 전값 중에 가장 작은 값 = tmamax
    tmparea = tmpmax * cnt # 중앙선을 포함한 직사각형의 넓이
    i = 0
    j = 0
    for _ in range(0, len(a) - 2):
        if d - 1 - i == 0: # i를 더 이상 못움직일 떄 
            j += 1
        elif d + j == len(a) - 1: # j를 더 이상 못 움직일 떄 
            i += 1
        else: # i,j가 범위안에 있다. 
            if a[d - 2 - i] >= a[d + 1 + j]: # 왼족에 녀석 높이가 오른쪽 보다 이상 일때 
                i += 1 # 밑변을 왼쪽으로 옮긴다. 
            else:
                j += 1 # 밑변을 오쪽으로 옮긴다. 
        tmpmax = min(tmpmax, a[d - 1 - i], a[d + j]) # 가장 작은 값을 높이로 두고 
        cnt += 1 # 밑변 길이를 만들어 
        tmparea = max(tmparea, tmpmax * cnt) # 넓이 비교 
    z = tmparea
    return max(divdeandconquer(x), divdeandconquer(y), z)

while True : #입력
    n, histogram = list(map(int, sys.stdin.readline().split()))
    if n == 0:
        break
    maxarea = divdeandconquer(histogram)
    print(maxarea)

 

 

 

 

코드 출처)

백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

이미지 참고 2)

File:Merge-sort-example-300px.gif - Wikimedia Commons

이미지 참고1)

(Divide and Conquer) - Google 검색