[Algorithm] Divide and conquer - Maximum Subarray

이번에는 분할 정복으로 해결할 수 있는 Maximum Subarray 문제를 알아보자.

 

Goal

 

주식 시장에서 가장 큰 수익을 얻기 위해서는 낮은 가격에 사서 높은 가격에 사는 것이 중요하다. 

다음 그래프를 보자. 어떤 상품의 가격을 날짜별로 나타내고 있고 Change는 그날 기준으로 전날과의 차이를 의미한다. 어떻게 이 문제를 해결할 수 있을까? 단순히 생각해 보면 주어진 표에서 가장 높은 가격과 가장 낮은 가격을 찾으면 된다.

 

하지만 여기에는 반례가 존재한다. 가장 높은 가격이 가장 낮은 가격보다 전에 해당하는 경우이다. 따라서 이 방법으로 모든 문제를 해결할 수 없다.

 

Solution #1, Brute-force solution

 

주어진 n개의 인스턴스 중에 2개를 고르는 모든 경우의 수를 따지는 방법이다. n 개 중에 2개를 고르는 경우의 수는

$$ \binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^{2}) $$ 

가 됨을 알 수 있다.

 

Solution #2, Divide and conquer

 

더 나은 방법이다. 부분합이 최대가 되게하는 방법을 분할 정복으로 해결할 수 있다는 것이 처음에는 의아하겠지만, 모든 알고리즘이 그렇듯 납득이 갈 것이다.

 

먼저 주어진 n개의 인스턴스를 담고 있는 배열을 생각해 보자. 우리가 결과적으로 알고 싶은 건 부분합이 최대가 되는 시작 인덱스, 끝 인덱스, 그리고 그때의 합이다. 합병 정렬처럼 가운데를 기준으로 나눈다면 정답이 될 수 있는 후보는

 

1. 왼쪽 서브 배열에 있거나,

2. 오른쪽 서브 배열에 있거나,

3. 왼쪽 서브 배열에 시작 인덱스가, 그리고 오른쪽 서브 배열에 끝 인덱스가 있는 경우

이다.

 

계속 Divide하다 보면 왼쪽 서브 배열과 오른쪽 서브배열의 합은 쉽게 구할 수 있을 것이다. 중요한 건 mid point를 가로지르는 경우의 부분합인데, 이때의 의사 코드를 살펴보자.

 

가운데를 중심으로 왼쪽을 향해 계속 더해 나가면서, 최댓값이 갱신되는 순간에만 시작 인덱스를 설정해 준다. 같은 방식으로 가운데를 중심으로 오른쪽을 향해 계속 더해 나가면서, 최댓값이 갱신되는 순간에만 끝 인덱스를 설정해 준다. 

 

결국 주어진 배열을 순차적으로 방문하는 것이기 때문에 $\theta(n)$의 시간 복잡도가 소요된다.

 

왼쪽과 오른쪽의 경우는 계속해서 Divide 되면서 base case까지 가는 $\Theta(lg n)$의 시간이 소요되고, 각각의 함수가 실행될 때마다 Crossing subarray 함수가 한 번씩 실행되므로 결국 이 경우에도 마찬가지로 $\Theta(n · lg n)$의 시간이 소요된다.

 

FIND-MAXIMUM_SUBARRAY 함수를 살펴보자. 먼저 1,2번 줄은 한 번 실행되므로 $\Theta(1)$ 이다. 이어서 4, 5번 줄은 같은 함수를 실행하므로 같은 시간복잡도를 가질 텐데, 할 때마다 요소의 개수가 반으로 줄어드니 $T(n/2)$에 해당하므로 $\Theta(lg n)$ 이다. 마지막으로 7 - 11번째 줄은 단 한번만 실행되므로 $\Theta(1)$ 이다.

 

$$T(n) = \begin{cases}\Theta(1) & \text{if } n = 1 \\ 2T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases} = \Theta(n · lg n) $$