[CLSR] 4.1 maximum subarray problem(Ch 4. divide-and-conquer)

특정 기간 내에 어떤 자산을 매수/매도를 해서 가장 높은 수익률을 내는 문제를 생각해 보자.

가장 낮은 가격이 등장한 뒤에 가장 높은 가격이 등장하면, 두 가격을 찾아서 매수/매도를 하면 되지만 일반적으로 그렇지 않다.

---

A brute-force solution

기간의 범위가 n개로 쪼개져있다고 했을 때 단순하게 모든 매수/매도 선택지에 대해 최대 수익률을 구하기 위해서는 $\binom{n}{2}$번의 연산을 해야 하고, 이는 $\Theta(n^2)$의 시간이 필요함을 의미한다.

이는 최악의 경우도 아니고 최선의 경우에도 모든 것을 찾는 것이므로 $\Omega(n^2)$의 시간으로 볼 수 있다.

---

A transformation

문제를 더 효율적으로 풀기 위해 우선 각 날짜의 '가격' 즉, 수준 변수 대신 날짜에 해당하는 '가격 변화분(day i의 가격 - day i-1의 가격 = $\triangle p_i$)'을 살펴보기로 한다.

각 날짜의 가격들로 배열을 만들 수 있는 것처럼 $\triangle p_i$로도 배열을 만들 수 있다. 또한, 배열의 '연속된 부분배열(contiguous subarray)' 중 sum이 가장 큰 부분 배열을 'maximum subarray'라고 하자.

그러면 maximum subarray를 찾는 문제는 가장 큰 수익률을 낼 수 있는 구간을 찾는 문제와 동일해진다.

이때도 brute-force한 방법으로 찾게 되면 결국 시간 복잡도의 개선이 이루어지는 것은 없다.

그래도 일차적으로 알 수 있는 것은 배열에서 음수값을 갖는 원소의 존재 여부가 중요하다는 점이다.

음수값이 없다는 것이 가격 하락 구간이 없다는 것이므로 maximum subarray는 배열 전체 그 자체가 된다.

---

A solution using divide-and-conquer

이 문제를 분할-정복 방식으로 풀어보려고 한다.

위에서 논하는 배열을 $A[low \cdots high]$라고 하자.

그리고 $mid$를 중간점이라 하면 기존 배열 $A$는 $A[low \cdots mid]$와 $A[mid + 1 \cdots high]$로 나누어질 수 있다.

그러면 원 배열 내의 모든 부분 배열 $A[i, j]$는 다음의 세 가지 경우로 나누어질 수 있다.

• 부분배열 $A[low \cdots mid]$에 온전히 속한 부분 배열. 즉, $low \leq i \leq j \leq mid$
• 부분배열 $A[mid +1 \cdots high]$에 온전히 속한 부분 배열. 즉, $mid  < i \leq j \leq high$
• 중간점을 지나는 부분 배열. 즉, $low \leq i \leq mid < j \leq high$

만약 앞 쪽 배열 내에서의 최대 부분 배열을 알고, 뒤쪽 배열 내의 최대 부분 배열을 알고, 중간점을 지나는 최대 부분 배열도 안다면, 셋 중 가장 큰 부분 배열을 배열 $A$의 최대 부분 배열이라 할 수 있다.

 

이것과 동일한 방식으로 $A[low \cdots mid]$와 $A[mid + 1 \cdots high$의 최대 부분 배열을 구할 수 있을 것이고 이러한 방식으로 문제를 분할하여 정복할 수 있다.

 

또한 중간점을 지나는 최대 부분 배열을 찾는 문제는 $A[i \cdots mid]$와 $A[mid + 1 \cdots j]$를 찾는 문제로 볼 수 있다.

이를 find_max_crossing_subarray라는 C 함수로 작성하면 다음과 같이 작성해볼 수 있다(책에 있는 수도코드를 C로 직역한 것으로 다소 비효율적일 수 있음).

void find_max_crossing_subarray(int A[], int low, int mid, int high,
int *max_left, int *max_right, int *sub_sum)
{
	int left_sum = -2147483648;
	int sum = 0;
	*max_left = mid;
	for (int i = mid; i >= low; i--)
	{
		sum = sum + A[i];
		if (sum > left_sum)
		{
			left_sum = sum;
			*max_left = i;
		}
	}

	int right_sum = -2147483648;
	sum = 0;
	*max_right = mid + 1;
	for (int j = mid + 1; j <= high; j++)
	{
		sum = sum + A[j];
		if (sum > right_sum)
		{
			right_sum = sum;
			*max_right = j;
		}
	}

	*sub_sum = left_sum + right_sum;
}

 $A$가 $n = high - low + 1$의 원소 갯수를 가지고 있으면 이 함수는 $\Theta(n)$의 시간이 걸린다고 할 수 있다.

 

작성한 함수를 바탕으로 핵심이 되는 find_maximum_subarray함수를 작성할 수 있다.

void find_maximum_subarray(int A[], int low, int high,
int *max_left, int *max_right, int *max_sum)
{
	int mid;
	int *left_max_left, *left_max_right, *left_max_sum;
	int *right_max_left, *right_max_right, *right_max_sum;
	int *cross_max_left, *cross_max_right, *cross_max_sum;

	if (high == low)
	{
		*max_left = low; *max_right = high; *max_sum = A[high];
	}
	else
	{
		mid = (low + high) / 2;
		find_maximum_subarray(A, low, mid, left_max_left, left_max_right, left_max_sum);
		find_maximum_subarray(A, mid + 1, high, right_max_left, right_max_right, right_max_sum);
		find_max_crossing_subarray(A, low, mid, high, cross_max_left, cross_max_right, cross_max_sum);

		if (*left_max_sum >= *right_max_sum && *right_max_sum >= *cross_max_sum)
		{
			*max_left = *left_max_left; *max_right = *left_max_right; *max_sum = *left_max_sum;
		}
		else if (*right_max_sum >= *left_max_sum && *left_max_sum >= *cross_max_sum)
		{
			*max_left = *right_max_left; *max_right = *right_max_right; *max_sum = *right_max_sum;
		}
		else
		{
			*max_left = *cross_max_left; *max_right = *cross_max_right; *max_sum = *cross_max_sum;
		}
	}
}

알고리즘의 시간 복잡도 계산의 편의를 위해 배열 원소의 갯수 $n$을 2의 멱수라고 하자.

$T(n)$을 배열이 $n$개의 원소를 가질 때 위 함수의 실행 시간이라고 하자.

 

우선 처음의 if문은 상수의 시간이 걸리므로 $n=1$일 때 $T(1) = \Theta (1)$이다.

 

$n>1$인 경우 재귀 호출이 일어난다.

$n=1$과 마찬가지로 if문에서 상수의 시간이 소요된다.

그리고 각 재귀에서 $T(n/2)$의 시간이 소요된다(2의 멱수 가정으로 인해 $n/2$는 항상 정수이다).

find_max_crossing_subarray는 $\Omega(n)$의 시간이 소요된다.

마지막 if, else if, else문은 항상 상수의 시간이 걸리므로 $\Omega(1)$의 시간이 걸린다.

따라서 위를 종합하면 $n>1$인 경우 소요 시간은 다음과 같다.

$$ \begin{equation} \begin{split} T(n) & = \Theta(1) + 2T(n/2) + \Theta(n) + \Theta(1)\\ &= 2T(n/2) + \Theta(n) \end{split} \end{equation}$$

 

결국 모든 케이스를 종합하면 다음과 같다.

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

 

뒤에 4.5단원에서는 위의 식에서 $T(n) = \Theta(n\, lg \, n)$의 결과를 도출할 것이다.