[알고리즘] 분할정복 (Divide and Conquer)

분할 정복

분할 정복은 그대로 해결하기 어려운 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀적으로 구한다. 그 후, 부분 문제의 답을 이용해 전체 문제의 답을 계산해낸다.

 

재귀 호출과 다른 점은 문제를 한조각과 나머지 전체로 나누는 대신, 거의 같은 크기의 부분 문제로 나눈다는 것이다. 

분할 정복이 필요한 문제의 예시로, 거듭 제곱을 구하는 알고리즘을 구현하면 다음과 같다.

def pow(a, b):
    res = 1
    for i in range(b):
        res *= a
    return res

단순 반복 연산으로 시간복잡도가 O(b)인 풀이이다. 분할 정복을 통해 더 빠르게 해결할 수 있다.

a, b, c = map(int, input().split())
def pow(a, b):
    if b == 0:
        return 1
    x = pow(a, b//2) 
    if b % 2 == 0:
        return (x%c) * (x%c) % c 
    else:
        return (x%c) * (x%c) * (a%c) % c

res = pow(a, b)
print(res)

해당 문제에 맞추어 구현하였다. 위 풀이를 통해 O(logb) 시간에 해결이 가능하다. 

---

이렇게 분할 정복으로 문제를 해결하고자 할 때, 문제를 부분 문제로 재정의하는 것이 어려울 수 있다. 이때 해결해야할 문제와 부분문제를 정확하게 정의하고, 부분 문제가 이미 해결되었다고 가정을 해야한다. 

하노이의 탑

예시로 재귀 문제로 유명한 하노이의 탑 문제를 풀어보자. 

1번 기둥에 있는 n개의 원판을 3번 기둥으로 최소 횟수로 옮겨야한다.
- 한 번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있을 수 없다. 

 

하노이의 탑의 전체 문제는 "n개의 원판을 1번 기둥에서 3번 기둥으로 옮긴다." 라고 정의할 수 있다.

 

이 때 n = 2 인 경우를 예시로 들면, 전체 문제를 다음과 같이 나눌 수 있다.

1. 큰 원판을 3번 기둥으로 옮기기 위해서, 작은 원판을 먼저 2번 기둥으로 옮긴다.
2. 큰 원판이 3번 기둥으로 옮긴 후, 작은 원판을 3번 기둥으로 옮긴다. 

 

이를 n > 2이라고 가정하고 부분문제를 정의하면 다음과 같다. 

1. 가장 큰 원판을 제외한 n-1개의 나머지 원판을 먼저 2번 기둥으로 옮긴다. n-1개의 원판을 옮기기 위해 중간지점으로 3번 기둥을 이용한다. 
2.  가장 큰 원판을 3번 기둥으로 옮긴 후, 2번 기둥에 있는 n-1개의 원판을 3번 기둥으로 옮긴다. n-1개의 원판을 옮기기 위해 중간지점으로 1번 기둥을 이용한다.

 

n = 2인 경우와 크게 다른 점이 없다. 이 때 부분 문제를 쉽게 정의하기 위해서, "n-1개의 원판을 3번 기둥을 이용해 2번 기둥으로 옮긴다." 는 부분 문제에서 더 깊게 들어가지 않는다. 이 부분은 재귀적으로 알아서 해결된다고 가정한다.

 

코드로 구현하면 다음과 같다.

def hanoi(n, begin, mid, end, answer):
    if n == 0:
        return answer
    hanoi(n-1, begin, end, mid, answer)
    answer.append([begin, end])
    hanoi(n-1, mid, begin, end, answer)
    return answer

def solution(n):
    answer = hanoi(n, 1, 2, 3, [])
    return answer
   
res = solution(2)
print(res)

---

합병 정렬

두 번째 예시로, 합병 정렬 문제 를 설계해보자. 

합병 정렬의 목표는 어떤 수열을 정렬하는 것이다. 이를 적절하게 문제를 분할할 수 있도록, 구간에 대한 정보를 추가해 문제를 다음과 같이 정의할 수 있다. 

어떤 수열의 from 부터 to 까지의 구간을 정렬시킨다. 

def sortArray(nums: list, from: int, to: int):
    pass

 

여기서 전체 문제를 풀이하는 함수 sortArray()를 부분 문제로 나누면 다음과 같다.

1. 수열을 from 부터 중간 지점까지의 구간을 정렬시킨다.
2. 수열을 중간 지점부터 to까지의 구간을 정렬시킨다.

def sortArray(nums: list, from: int, to: int):
    mid = from + (to - from) // 2
    sortArray(nums, from, mid)  # from부터 mid까지의 구간은 정렬되어 반환된다.
    sortArray(array, mid + 1, to)  # mid+1부터 to까지의 구간은 정렬되어 반환된다.​

정의한 두 부분 문제가 해결되었다고 가정하면, 전체 수열을 정렬하는 것은 정렬된 두 수열을 합치면 끝난다. 정렬된 두 수열을 합쳐 정렬하는 것은 O(n)에 해결 가능하다.

정렬된 두 수열을 정렬된 상태로 합친다.

# 정렬된 수열 left와 right가 있을 때, 
# 두 수열의 원소를 비교해가며 더 작은 값을 취하며 정렬한다. 

merged = []
l = 0 
r = 0

while l < len(left) and r < len(right):
    if left[l] < right[r]:
        merged.append(left[l])
        l += 1
    else:  
        merged.append(right[r])
        r += 1​

 

정리하자면 우리는 정렬 문제를 '구간' 을 통해 부분 문제로 분할하였으며, 부분 문제에 대한 해답을 merge하는 작업을 통해 전체 문제에 대한 해답을 얻을 수 있다. 이를 재귀적으로 구현만 하면 된다. 

 

전체 코드는 다음과 같다. (구간 분할은 위 예시처럼 따로 변수를 두지 않고 slicing으로 구현하였다.)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) == 1:
            return nums

        m = len(nums) // 2

        left = self.sortArray(nums[:m])
        right = self.sortArray(nums[m:])
        
        merged = []
        l = 0 
        r = 0

        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                merged.append(left[l])
                l += 1
            else:  
                merged.append(right[r])
                r += 1
        
        merged += left[l:]
        merged += right[r:]

        return merged

분할 정복을 통해 합병 정렬은 최종적으로 최악의 경우에도  O(nlogn)의 시간복잡도를 갖는다. 

---

추가 문제

쿼드 압축

프로그래머스

전체 문제: 2^n x 2^n 크기의 arr에서 0과 1의 개수를 찾는 것
부분 문제: 2^(n-1) x 2^(n-1) 크기의 arr에서 0과 1의 개수를 찾는 것

def solution(arr):
    n = len(arr)
    answer = quad_tree(arr, (0,0), (n-1, n-1))
    return answer


def quad_tree(arr, begin, end):
    zero_cnt = 0
    one_cnt = 0
    n = end[0] - begin[0] + 1 # board size
    for i in range(begin[0], end[0]+1, 1):
        for j in range(begin[1], end[1]+1, 1):
            if arr[i][j] == 0:
                zero_cnt += 1
            else:
                one_cnt += 1
    if zero_cnt == n**2:
        return [1, 0]
    elif one_cnt == n**2:
        return [0, 1]

    mid = (begin[0] + n // 2 -1, begin[1] + n // 2 - 1)
    divide = [
        (begin, mid),
        ((begin[0], mid[1] + 1), (mid[0], end[1])),
        ((mid[0] + 1, begin[1]), (end[0], mid[1])),
        ((mid[0] +1, mid[1]+1), end)
    ]

    cnt_sum = [0, 0]
    for b, e in divide:
        cnt = quad_tree(arr, b, e)
        cnt_sum[0] += cnt[0]
        cnt_sum[1] += cnt[1]

    return cnt_sum

if __name__ == '__main__':
    arr = [[1,1,0,0],
           [1,0,0,0],
           [1,0,0,1],
           [1,1,1,1]]
    res = solution(arr)
    print(res)