1-(4) Divide and Conquer-(i) The maximum-subarray problem

이 챕터에서는 Divide & conquer 방법과 그것을 적용하여 풀이할 수 있는 예제인 maximum-subarray problem을 소개하고 있다. Divide&conquer에 대해서는 1-(2) MergeSort에서 다루었으므로 이 글에서는 문제 소개와 그 풀이만 하도록 하겠다.

*이 글의 흐름은 예전에 수강했던 심규석 교수님의 프로그래밍 방법론 수업 흐름을 거의 그대로 활용하였음을 알린다. 책에는 linear time solution이 제시되어있지 않아서 그 부분을 교수님의 강의를 들은 기억을 활용해서 썼다.

문제: 주어진 배열 A[1:n]에 대해 그 subarray A'=A[k:l]을 생각해볼 수 있다.(k>=1,l<=n)

이 때 가능한 모든 subarray A'에 대해 A'이 갖는 모든 원소의 합 arraySum(A')에 대해 최대인 arraySum(A')은 얼마인가?

즉,

입력: A[1:n]

출력: max(arraySum(A'))

 

(1)Brute-force

그냥 무식하게 할 수 있다. 가능한 모든 arraySum(A')을 구해나가면서 max를 갱신하면 된다. 다음은 그 코드와 설명이다.

<그림1: 아래 코드의 인덱스 설명>

int max_sum1(int* arr,int size) { //O(n^3) algorithm, brute_force algorithm
	int sum = 0;
	int maxsum = -INFINITE;
	for (int i = 0; i < size; i++) { // i is start point of range
		for (int j = i; j < size; j++) { //j is end point of range
			sum = 0; //have to clear sum whenever calculate new sum of range
			for (int k = i; k <= j; k++) { //for loop that calculate sum of range
				sum += arr[k]; 
			}
			if (sum > maxsum) maxsum = sum; //renewal of maxsum
		}
	}
	return maxsum;
}

이런 경우 삼중 포문이고 각 loop가 최대 n번씩 도는 경우가 존재하므로 T(n)=O(n³)이다. 데이터가 클 때 쓸만한 알고리즘은 아닌 것 같다. 그렇다면 어떻게 이것을 줄여볼 수 있는가?

그런데 가장 안쪽의 for loop는 subarray의 합을 계산하기 위한 것인데 다음<그림2>를 보면 j가 움직일 때 그 다음 step의 sum은 이전 step sum(주황색)에 arr[j](빨강색)를 더한 것이다. 따라서 이것을 이용하면 각 sum을 계산하는데 이용되는 가장 안쪽의 for loop를 const한 시간이 걸리는 계산으로 바꿀 수 있다.

<그림2: sum 계산 쉽게하기>

//O(n^2) algorithm
int max_sum2(int* arr, int arrsize)
{
	int max_sum = 0;
	int arr_sum = 0;
	for (int i = 0; i < arrsize; i++) {
		arr_sum = 0;
		for (int j = i; j < arrsize; j++) {
			arr_sum += arr[j];
			if (arr_sum > max_sum) max_sum = arr_sum;
		}
	}
	return max_sum;
}

이 경우 중첩된 loop가 하나 줄었으므로 걸리는 시간은 O(n²)이 된다. 

 

(2)Divide&Conquer

시간을 더 줄여볼 수는 없는가? 책에서는 Divide and Conquer를 그 방법으로 제시하고 있다. 다음 <그림3>을 보자.

<그림3: Divide & conquer 방법>

만약 mid를 기준으로 왼쪽 배열의 subarray sum최댓값인 leftMax와 오른쪽 배열의 subarray sum최댓값인 rightMax를 알고 있다면 우리는 어떻게 전체 배열의 subarray sum을 구할 수 있는가? 가장 먼저 드는 생각은 leftMax와 rightMax를 비교해보는 것이겠지만, 이렇게 두 개만 비교하면 놓치는 경우가 생긴다. 그것은 max sum을 갖는 subarray가 왼쪽 배열과 오른쪽 배열에 걸쳐 있는 경우인데 이런 경우를 고려하기 위해 crossMax를 계산해서 총 3개의 Max값을 비교해야 전체 배열의 최댓값을 구할 수 있다.

 

leftMax와 rightMax는 작은 subarray에 대한 algorithm의 해이기 때문에 recursive하게 구해질 수 있고, 따라서 추가적으로 구현에 신경써야 할 것은 CrossMax를 계산하는 부분이다. CrossMax는 어떻게 계산할까? 가장 쉬운 방법은 leftMax에서 start point i rightMax에서 end point j를 잡아서 그 내부의 sum을 계산해주는 방법이다. 이렇게 계산하면 start point와 end point가 각각 n/2개 이므로 총 n²/4번의 연산을 수행해야 하는데, 이러면 벌써 n²가 나오므로 brute-force한 방법과 차이가 없다. 따라서 이 CrossMax를 효율적으로 계산할 방법을 생각해봐야 한다.

 

사실, 한 가지 FACT만 생각해보면 이 연산이 n번이면 된다. 위에서 mid를 end point로 갖는 subarray들의 집합 L={A''|A''=A[l:mid] for all l<=mid}과 mid+1을 start point로 갖는 subarray들의 집합 R={A''|A''=A[mid+1:r] for all r>=mid+1}에서 L과 R의 maxSum인 leftCrossMax, rightCrossMax를 생각해보자. 이 때 다음 사실이 성립함을 귀류법에 을 이용해 쉽게 증명할 수 있다.

 

"CrossMax는 leftCrossMax와rightCrossMax의 합이다."

 

따라서 leftCrossMax를 구하는데 많아도 n/2번 보면 되고 rightCross를 구하는데 많아도 n/2번이므로 n time안에 이 연산이 가능하다. 따라서 time complexity는 다음과 같다.

T(n)=T(n/2)+n

풀어보면 T(n)=O(nlog₂n)이 나온다. Code와 설명은 다음과 같다. CrossMax를 구하는 것, 세 개의 수 중 Max를 구하는 연산은 다른 함수로 빼서 구현했다.

int determineMax(int a, int b, int c=-INFINITE) { //return max number in set of {a,b,c}
	if (a > b) {
		if (a > c) return a;
		else return c;
	}
	else { //a<b
		if (b > c) return b;
		else return c;
	}
}
int crossMaxSum(int* arr, int start, int mid, int end) { //subfunction for max_sum3
	int tempSum = 0;
	int leftMaxSum = -INFINITE;
	int rightMaxSum = -INFINITE;
	//1. calculate left maxsum
	for (int i = mid; i >= start; i--) {
		tempSum += arr[i];
		if (tempSum > leftMaxSum) leftMaxSum = tempSum;
	}
	//2. calculate right Maxsum
	tempSum = 0;
	for (int i = mid + 1; i <= end; i++) {
		tempSum += arr[i];
		if (tempSum > rightMaxSum) rightMaxSum = tempSum;
	}
	return (leftMaxSum + rightMaxSum);
}

int max_sum3(int* arr,int start, int end) { //O(nlgn) algorithm, using divide & conquer method
	if (start == end) return arr[start]; //basis case
	else { //recursion case
		int mid = (start + end) / 2;
		int leftMaxSum = max_sum3(arr, start, mid);
		int rightMaxSum = max_sum3(arr, mid + 1, end);
		int CrossMaxSum = crossMaxSum(arr, start, mid, end);
		return determineMax(leftMaxSum, rightMaxSum, CrossMaxSum);
	}
}

 

(3)Incremental

Divide & conquer단원이지만 insertion sort를 짤 때 활용했던 incremental 방법을 생각해보자. 이걸 쓰면 O(n)까지 줄어든다.

현재 arr[1:i-1]까지 maxSum이 주어져있는 상황이라 해보자. 이 때 i step에서 Divide and conquer를 생각해보면 left배열을 arr[1:i-1] right 배열을 arr[i]단 하나로 볼 수 있을 것이다. 그럼 다음 세가지를 고려하면 된다.

1)leftMax = maxSum of previous step

2)CrossMax = leftCrossSum+arr[i]

3)rightMax = arr[i]

이 때 leftCrossSum은 항상 0보다 크거나 같기 때문에 2)는 3)보다 크거나 같고 따라서 1)과 2)만 비교하면 된다. 따라서 이전 step에서 leftCrossSum과 maxSum이 주어진다면 T(n)=T(n-1)+1로 linear time이 된다.

leftCrossSum은 기본적으로 원소들을 매 스텝마다 계속 더해나가다가 0아래가 되면 0으로 갱신해주기만 하면 된다. 이를 code로 구현하면 다음과 같은데, 두 번째 함수는 recursion을 이용한 것이다.

int max_sum4(int* arr, int size) { //O(n) algorithm, using incremental method
	int thisSum = 0;
	int maxSum = -INFINITE;
	for (int i = 0; i < size; i++) {
		if (maxSum < thisSum + arr[i]) {
			maxSum = thisSum + arr[i];
		}
		thisSum += arr[i];
		if (thisSum < 0) thisSum = 0;
	}
	return maxSum;
}
int max_sum5(int* arr, int end, int& thisSum) { //using recursion
	if (0 == end) {
		thisSum = (arr[end] > 0) ? arr[end] : 0;
		return arr[end]; //basis case of recursion
	}
	else {
		int maxSum = max_sum5(arr,end-1,thisSum);//maxSum of previous step
		if (maxSum < thisSum + arr[end]) maxSum = thisSum + arr[end];
		thisSum += arr[end];
		if (thisSum < 0) thisSum = 0;
		return maxSum;
	}
}

Test Code를 포함한 전체 코드는 다음과 같다.

#include<iostream>
#include<time.h>
#define INFINITE 100000
using namespace std;

int max_sum1(int* arr,int size) { //O(n^3) algorithm, brute_force algorithm
	int sum = 0;
	int maxsum = -INFINITE;
	for (int i = 0; i < size; i++) { // i is start point of range
		for (int j = i; j < size; j++) { //j is end point of range
			sum = 0; //have to clear sum whenever calculate new sum of range
			for (int k = i; k <= j; k++) { //for loop that calculate sum of range
				sum += arr[k]; 
			}
			if (sum > maxsum) maxsum = sum; //renewal of maxsum
		}
	}
	return maxsum;
}

int max_sum2(int* arr, int size) { //O(n^2) algorithm, delete for loop that calculate sum of range in max_sum1
	int sum = 0;
	int maxsum = -INFINITE;
	for (int i = 0; i < size; i++) {
		sum = 0;
		for (int j = i; j < size; j++) {
			sum += arr[j];
			if (sum > maxsum) maxsum = sum;
		}
	}
	return maxsum;
}
int determineMax(int a, int b, int c=-INFINITE) { //return max number in set of {a,b,c}
	if (a > b) {
		if (a > c) return a;
		else return c;
	}
	else { //a<b
		if (b > c) return b;
		else return c;
	}
}
int crossMaxSum(int* arr, int start, int mid, int end) { //subfunction for max_sum3
	int tempSum = 0;
	int leftMaxSum = -INFINITE;
	int rightMaxSum = -INFINITE;
	//1. calculate left maxsum
	for (int i = mid; i >= start; i--) {
		tempSum += arr[i];
		if (tempSum > leftMaxSum) leftMaxSum = tempSum;
	}
	//2. calculate right Maxsum
	tempSum = 0;
	for (int i = mid + 1; i <= end; i++) {
		tempSum += arr[i];
		if (tempSum > rightMaxSum) rightMaxSum = tempSum;
	}
	return (leftMaxSum + rightMaxSum);
}

int max_sum3(int* arr,int start, int end) { //O(nlgn) algorithm, using divide & conquer method
	if (start == end) return arr[start]; //basis case
	else { //recursion case
		int mid = (start + end) / 2;
		int leftMaxSum = max_sum3(arr, start, mid);
		int rightMaxSum = max_sum3(arr, mid + 1, end);
		int CrossMaxSum = crossMaxSum(arr, start, mid, end);
		return determineMax(leftMaxSum, rightMaxSum, CrossMaxSum);
	}
}
int max_sum4(int* arr, int size) { //O(n) algorithm, using incremental method
	int thisSum = 0;
	int maxSum = -INFINITE;
	for (int i = 0; i < size; i++) {
		if (maxSum < thisSum + arr[i]) {
			maxSum = thisSum + arr[i];
		}
		thisSum += arr[i];
		if (thisSum < 0) thisSum = 0;
	}
	return maxSum;
}
int max_sum5(int* arr, int end, int& thisSum) { //using recursion
	if (0 == end) {
		thisSum = (arr[end] > 0) ? arr[end] : 0;
		return arr[end]; //basis case of recursion
	}
	else {
		int maxSum = max_sum5(arr,end-1,thisSum);//maxSum of previous step
		if (maxSum < thisSum + arr[end]) maxSum = thisSum + arr[end];
		thisSum += arr[end];
		if (thisSum < 0) thisSum = 0;
		return maxSum;
	}
}

int main()
{
	int arrsize;
	cout << "Enter size of array: ";
	cin >> arrsize;
	const int range = 10000;
	int* arr = new int[arrsize];
	double m_ratio = 0.5;	//Change the ratio of negative numbers

	srand((unsigned int)time(NULL));
	for (int i = 0; i < arrsize; i++)
	{
		arr[i] = rand() % range - int(m_ratio * range);
	}

	int sum1, sum2, sum3, sum4, sum5, this_sum;
	clock_t begin, end;

	begin = clock();
	sum1 = max_sum1(arr, arrsize);
	end = clock();
	cout << "O(n^3) algorithm\n" << "Max sum : " << sum1 << endl;
	cout << "Elapsed time : " << (end - begin) << "ms"<< endl;

	begin = clock();
	sum2 = max_sum2(arr, arrsize);
	end = clock();
	cout << "O(n^2) algorithm\n" << "Max sum : " << sum2 << endl;
	cout << "Elapsed time : " << (end - begin) << "ms" << endl;

	begin = clock();
	sum3 = max_sum3(arr, 0, arrsize - 1);
	end = clock();
	cout << "O(nlogn) algorithm\n" << "Max sum : " << sum3 << endl;
	cout << "Elapsed time : " << (end - begin) << "ms" << endl;
	
	begin = clock();
	sum4 = max_sum4(arr, arrsize);
	end = clock();
	cout << "O(n) algorithm\n" << "Max sum : " << sum4 << endl;
	cout << "Elapsed time : " << (end - begin) << "ms" << endl;
	
	begin = clock();
	sum5 = max_sum5(arr, arrsize - 1, this_sum);
	end = clock();
	cout << "O(n) recursion algorithm\n" << "Max sum : " << sum5 << endl;
	cout << "Elapsed time : " << (end - begin) << "ms" << endl;

	system("PAUSE");
	return 0;
}

n=8000으로 했을 때 그 결과는 아래와 같다.

다음 글에서는 Heap에 대해 알아본다.