[알고리즘] - Divide and Conquer

오늘은 알고리즘에서 말하는 divide and conquer 개념에 대해서 알아보자. Dynamic Programming을 들어가기 앞서서 알아두어야 할 문제해결 방법론이다.

---

Divide and Conquer란 무엇인가? 바로, 주어진 문제를 여러 개의 단위로 쪼개서 해결한 뒤 해결된 것들을 합쳐서 최종적인 output을 낸다는 아이디어다. 그렇다면 여기서 해야 할 것은 무언인가? 바로, 독립적으로 해결 가능한 subproblem을 정의하고 optimal substructure를 정의하는 것이다. 독립적으로 해결 가능한 subproblem이라 함은 주어진 문제를 쪼갰을 때, 그 쪼갠 두 문제가 서로 독립적이어야 한다는 것이다. 그래야 서로 영향을 주지 않고, 두 문제 모두 해결하여 그 output을 합쳤을 때 output이 나올 수 있다. 그리고, optimal한 substructure라고 함은 subproblem에서 사용할 자료구조에 해당한다. 어떤 식으로 주어진 input을 배치할 것인지에 대한 정의를 말한다.

위의 두가지가 정의가 되면, 그때부터 recurrence를 이용하고, memoization 방법까지 포함하면 Dynamic Programming(DP)이 된다.

Divide and Conquer의 간단한 예시 문제를 보자.

주어진 배열에서 [10, 1, 0, -9, 8, 4, 7, 6, ...] 최대값 M과 최소값 m의 차이를 극대화 하되, 최대값의 index는 최소값의 index보다 작아야 한다.

위의 문제는 그럼 어떻게 풀 수 있을까? 간단히 생각하면 모든 순서를 하나씩 다 살펴가면서 가장 크게 되는 조합을 찾는 방식인데, 그럴 경우 알고리즘의 복잡도가 최대 $O(n^2)$이 될 수 있다. 일단 exponential이 되기 때문에 그렇게 썩 좋지는 않다. 이보다 더 잘할 수 있는 방법이 바로 재귀를 이용하는 것이다. 먼저 위에서 말한 것처럼 1) subproblem을 정의하고, 2) optimal substructure를 정의해보도록 하자.

1. subproblem 정의
   이 배열을 반으로 나누었을 때, 각 구간 별로 최대, 최소가 다 포함되어 있는 경우가 있겠고, 마지막으로 반으로 나눈 구간의 왼쪽에 최대값이, 오른쪽에 최소값이 있는 세가지 경우를 생각해볼 수 있다.

2. 그렇다면 optimal substructure는?
   어차피 배열을 반으로 쪼개서 위의 문제를 또다시 진행하면 되기 때문에 우리가 원하는 문제는 재귀를 통해서 풀리게 된다. 이를 아래의 수식으로 표현해볼 수 있는데,

$$C[n] = max(C_{left}[n/2], C_{right}[n/2], (findmax(n/2)-findmin(n/2))$$

즉 주어진 n개의 배열에 대해서 알고리즘 $C(\cdot)$은 배열을 반으로 쪼개서 다시 $C(\cdot)$을 호출시키고, 그리고 마지막 경우를 위해서 왼쪽 구간의 max 값과 오른쪽 구간의 min 값을 구해서 그 차이가 최대가 되는 값을 반환하는 것이다. 이렇게 하면 복잡도가 어떻게 될까?

재귀함수에서 복잡도 계산은 조금 복잡하긴 한데 간단히 master method를 이용하여 설명만 하자면 $T(n) = a \cdot T(n/b) + f(n)$ 으로, 여기서 $T(n)$은 재귀 알고리즘을 말하고, a와 b는 각각 subproblem이 생성되는 갯수(여기서는 2개), 그리고 n/b는 subproblem의 사이즈를 말한다.(여기서 b도 2다). 그리고 $f(n)$은 나뉘었던 문제들을 합치는데 걸리는 시간을 말한다. 이 문제에서는 재귀와 결과들을 합치는데 걸리는 시간이 비슷하다. 그럴 경우에는 알고리즘의 복잡도는 $T(n) = \Theta (n^{c_{crit}}\log^{k+1} n)$ 이 되고, 우리의 예시의 경우 $n\log n$이 된다. 이는 기존의 방법인 $O(n^2)$ 보다 더 빠른 방법이다.

그렇다면 오늘은 여기까지!