[분할정복] Divide and Conquer

Divide and Conquer

 

• Top-Down 방식의 알고리즘
• Divide : 가장 상위의 문제를 2개의 하위 단계의 문제로 나눈다.
• Conquer : 최적의 부분 구조까지 문제를 나눈 후 해결한다.
• Combine : 하위 문제에 대한 결과를 조합한다.

Divide and Conquer

 

예시1) MergeSort(병합정렬)

 

• 기존 Selection sort, Bubble sort, Insertion sort의 시간복잡도 O(N^2)
• Merge sort의 시간복잡도 O(NlogN)
• 병합 정렬의 알고리즘 및 분할 정복 개념 적용

1. 데이터 크기가 2 이상일 때, 데이터를 두 집합으로 분할 ( Divide )
2. 데이터의 크기가 0 또는 1이면 정렬된 데이터
3. 데이터를 모두 분할한 후, 데이터 집합들을 병합 ( Combine )
4. 병합 과정에서 데이터를 정렬하면서 병합 ( Conquer )

• MergeSort 구현 ( Python )

import sys
input = sys.stdin.readline

n = int(input())
num_list = list(map(int,input().split()))
k = int(input())

def mergeSort(ls) :

    if len(ls) <= 1 :
        return ls

    mid = len(ls) // 2
    # Divide
    left_ls = mergeSort(ls[:mid])
    right_ls = mergeSort(ls[mid:])
    # Conquer&Combine
    merge_ls = merge(left_ls, right_ls)
    return merge_ls

#Conquer
def merge(ls1, ls2):
    merge_ls = list()
    print(ls1, ls2)
    while len(ls1) > 0 and len(ls2) > 0:
        if ls1[0] <= ls2[0]:
            merge_ls.append(ls1.pop(0))
        else:
            merge_ls.append(ls2.pop(0))
    if len(ls1) > 0:
        merge_ls += ls1
    if len(ls2) > 0:
        merge_ls += ls2
    print(merge_ls)
    return merge_ls

mergeSort(num_list)

# 입력
8
1 5 2 4 2 9 7 3


# 결과
[1] [5]
[1, 5]
[2] [4]
[2, 4]
[1, 5] [2, 4]
[1, 2, 4, 5]
[2] [9]
[2, 9]
[7] [3]
[3, 7]
[2, 9] [3, 7]
[2, 3, 7, 9]
[1, 2, 4, 5] [2, 3, 7, 9]
[1, 2, 2, 3, 4, 5, 7, 9]

 

예시2) 부분수열의 합 1, 2

 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

• 부분 수열의 합 1

N<=20 이므로 itertools의 combination을 통해 모든 조합의 경우를 brute force로 계산해도 2^20 = 1024*1024 = 약 1,000,000으로 문제의 시간 안에 충분히 들어올 수 있음

 

• 부부 수열의 합 2

N<=40 이므로 위와 같이 모든 경우를 계산하면 백만 * 백만으로 절대 문제의 시간 제한 안에 들어올 수 없음.

이때, 분할 정복 개념을 이용하여 각 집합을 절반으로 나눠서 해결. 이때, 부분 수열의 합 1에서 사용했던 해결 방법을 활용해서 N<=20인 두 개의 집합으로 나눠 해결.

 

풀이 코드

# 부분 수열의 합 1
# coding = utf-8

if __name__ == '__main__':
    import sys

    input = sys.stdin.readline
    from collections import deque
    from itertools import *


    def getdata():
        n, s = map(int,input().split())
        board = list(map(int, input().split()))
        return n, s, board

    n,s,board= getdata()
    res = 0
    for i in range(1, n+1) :
        for choice in combinations(board, i) :
            if sum(choice) == s:
                res += 1

    print(res)

# 부분 수열의 합 2
# coding = utf-8

import sys
input = sys.stdin.readline
from itertools import combinations
import bisect

n, s = map(int,input().split())
ls = list(map(int,input().split()))

ll, lr = list(), list()

for i in range(len(ls[:(n//2)])+1) :
    for choice in combinations(ls[:(n//2)], i) :
        ll.append(sum(choice))

for i in range(len(ls[(n//2):])+1) :
    for choice in combinations(ls[(n//2):], i) :
        lr.append(sum(choice))

ll.sort()
lr.sort()
# print(ll, lr)
ans = 0
for lnum in ll :
    l = bisect.bisect_left(lr, s-lnum)
    r = bisect.bisect_right(lr, s-lnum)
    ans += r-l
if s == 0 :
    ans -= 1
print(ans)

 

예시3) Closest Pair Problem

 

• 최근접 점의 쌍 문제
• 2차원 평면 상의 n개의 점 중 거리가 가장 가까운 한 쌍의 점을 찾는 문제
• Brute force - O(n^2)
• Divide and Conquer을 사용하여 O(nlogn)으로 구현 가능

1. 집합의 크기가 3이하일 때까지 두개의 집합으로 분할
2. 집합 내에서 brute force로 가장 거리가 작은 두개의 점 선택
3. 왼쪽 집합과 오른쪽 집합에서 min값 구한 후, 중간 영역에서 가장 짧은 거리 두점 계산
4. 셋 중 가장 짧은 거리로 conquer후 combine