이번 시간엔 최대부분배열을 구현해보자.

1. 문제

• 길이가 n인 배열 A[0], A[1], ..., A[n-1] 이 입력으로 주어 질때, i번째부터 j번째까지 원소드로 이루어진 배열 A[i], ..., A[j] 를 부분배열이라고 하고, A[i, j] 로 나타낸다.

• 부분 배열의 속한 원소들의 합이 최대가 되는 부분 배열을 구하는 것이 이 문제의 목적이다.

이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다.

예를 들어, 아래와 같은 배열이 있다면,

-2 -1 3 5 2 -5 0 2면 이 배열의 최대부분배열의 합은 10이다(3+5+2)

2. 해결방법

• 최대부분배열의 원소합을 구하는 알고리즘에는 크게 4개가 있다.

• 완전탐색, 중복제거한 탐색, 분할정복법, 동적계획법

1) 완전탐색(브루트포스 알고리즘) - 시간복잡도 O(n^3)

• 단순히 모든 부분배열을 비교하여 최대인 배열을 구하는 알고리즘이다.

• MaxSum은 최종 결과합, ThisSum은 각 부분배열의 합을 저장하는 변수

• 삼중반복문을 이용하여 i(0,n)~j(i,n)까지의 부분배열을 구한다.

int MaxSubarray1(int A[], int N)
{
	int MaxSum, ThisSum; 
	int i, j, k;
	MaxSum = 0;
	for (i = 0; i < n; i++) {
		for (j = i; j < n; j++) {
			ThisSum = 0;
			for (k = i; k <= j; k++)
				ThisSum = ThisSum + A[k];
			MaxSum = max(MaxSum, ThisSum);
		}
	}
	return MaxSum;
}

- 시간복잡도 구하기

시간복잡도는 명령실행개수를 구하는 것!

데이터의 개수가 n개일 때 for문 하나당 O(n) 시간이 걸린다고 생각하면 편함(for문 안이 상수시간이 걸릴 때)

따라서 3중 반복문이므로 O(n x n x n) = O(n^3) 이다.

• 특징 : 시간복잡도가 O(n^3) 이기 때문에 데이터의 개수가 많아질수록 시간이 기하급수적으로 오래 걸림

2) 중복을 제거한 탐색

• 1번 방법에서 중복을 제거한 방법이다

• 1번 방법에서는 모든 부분배열의 원소의 합을 각각 다 구하기 때문에 중복계산이 많다

예를 들어 [0,2]의 부분배열의 합([0]+[1]+[2])을 구해도 다음번 [0,3]의 부분배열은 [0]+[1]+[2] 의 연산을 다시해야 한다.

이 것을 보완한 알고리즘이 2번 알고리즘이다.

int MaxSubarray2(int A[], int N)
{
	int MaxSum, ThisSum;
	int i, j;
	MaxSum = 0;
	for (i = 0; i < n; i++) {
		ThisSum = 0;
		for (j = i; j < n; j++) {
			ThisSum = ThisSum + A[j];
			MaxSum = max(MaxSum, ThisSum);
		}
	}
	return MaxSum;
}

- 시간복잡도 구하기

이중반복문이므로 O(n^2) 이 걸린다. (1번참고)

이 알고리즘 또한 데이터의 개수가 많아질수록 시간이 기하급수적으로 오래걸린다.

3) 분할정복법

• 부분배열의 중간값의 인덱스를 k(임의의 수)라고 했을때

• k보다 왼쪽에 있으면 left, 오른쪽에있으면 right라고 하자.

• 그러면 모든 부분배열은 left에 있는 부분배열, right에 있는 부분배열, left와 right에 걸쳐있는 부분배열 중 하나일 것

  ex: 0 1 2 3 k=4 5 6 7 8

• 예를 들면 0~3에 있는 부분배열 ,5~8에 있는 부분배열, 4를 포함하여 걸쳐있는 부분배열 이 있을 것이다.

• 그러면 순환호출(재귀)를 이용하여 각각에 속해있는 부분배열의 합을 구할 수 있다.

  (left에 있는 부분배열을 중간값을 정해 left안의 left, right를 구하고.. .또 구하고. 이런식으로)걸쳐있는 부분배열은? -> 왼쪽과 오른쪽의 부분배열을 합치면 된다!
  

- 그러면 최대부분배열은? (key)

왼쪽에서의 부분배열의 최대값과 오른쪽에서의 부분배열의 최대값과 왼쪽과 오른쪽에 걸친 부분배열을 비교하여

가장 큰 값이 전체배열의 최대부분배열의 원소의 합이 될 것이다.

다음 이미지를 보자,

int MaxSubarray3(int A[], int Left, int Right)
{
	int MaxSum, MaxLeft, MaxRight, MaxCenter;
	int MaxCenterL, MaxCenterR, ThisSum;
	int Center, i;
	if (Left == Right) {
		if (A[Left] > 0) return A[Left];
		else return 0;
	}
	Center = (Left + Right) / 2;
	MaxLeft = MaxSubarray3(A, Left, Center);
	MaxRight = MaxSubarray3(A, Center + 1, Right);
	MaxCenterL = 0;
	ThisSum = 0;
	for (i = Center; i >= Left; i--) {
		ThisSum = ThisSum + A[i];
		MaxCenterL = max(MaxCenterL, ThisSum);
	}
	MaxCenterR = 0;
	ThisSum = 0;
	for (i = Center + 1; i <= Right; i++) {
		ThisSum = ThisSum + A[i];
		MaxCenterR = max(MaxCenterR, ThisSum);
	}
	MaxCenter = MaxCenterL + MaxCenterR;
	MaxSum = max(max(MaxLeft, MaxRight), MaxCenter);
	return MaxSum;
}

먼저 함수의 인수를 보자.

A[] 은 입력된 배열, left는 가장 왼쪽에 있는 인덱스 0, right는 가장 끝쪽에 있는 인덱스 n-1이 될 것이다.

(왜냐하면 배열의 크기가 n이므로 가장 끝에 있는 배열의 인덱스는 n-1)

선언된 변수를 보자.

MaxSum = 최종 부분배열원소의 최대값

MaxLeft = 왼쪽에 있는 부분배열의 최대값

MaxRight = 오른쪽에 있는 부분배열의 최대값

MaxCenter = 양쪽에 걸쳐있는 부분배열의 최대값

MaxCenterL = 왼쪽배열의 부분배열의 최대값

MaxCenterR = 오른쪽배열의 부분배열의 최대값

(조건문)

if (Left == Right) {
		if (A[Left] > 0) return A[Left];
		else return 0;
	} 
  왼쪽과 오른쪽의 인덱스가 같을 때이다. 즉 배열의 크기가 1일 때 재귀함수가 끝난다.

(중앙값(k) Left와 Right의 평균값)

Center = (Left + Right) / 2;
	MaxLeft = MaxSubarray3(A, Left, Center);
	MaxRight = MaxSubarray3(A, Center + 1, Right);
	MaxCenterL = 0;
    
 순환 호출을 이용하여 구하려는 배열의 크기가 0이 될 때까지 부분배열을 구한다.
 

(반복문)

for (i = Center; i >= Left; i--) {
		ThisSum = ThisSum + A[i];
		MaxCenterL = max(MaxCenterL, ThisSum);
	}
    
i가 center부터 left까지 감소하면서 부분배열의 합을 구한다.

그리고 합을 구하면서 부분배열의 최대값을 구한다.

MaxCenter = MaxCenterL + MaxCenterR;
	MaxSum = max(max(MaxLeft, MaxRight), MaxCenter);
    
    
 걸쳐있는 배열은 left배열에서의 최대값과 right배열에서의 최대값을 더한 값

최종 결과값은 left, right, center에서 가장 큰 값이 최대부분배열의 원소의 합이 된다.   

시간복잡도 구하기

T(n) 을 길이가 n인 배열에서 최대 부분 배열을 구하는 데 걸리는 시간이라고 하자.

n=1 일때(배열의 크기가 1일때) 에는 left랑 right가 (0일때)같을 때 즉 if문을 수행하므로 상수시간(O(1)) 이다.

n>=2 인 경우에는 배열을 반으로 나누어 n/2인 배열 각각에 대해 순환호출을 한다.

두개의 for문을 수행하는데 각각 O(n)시간 걸리므로

총 걸리는 시간 T(n) =2*T(n/2)(순환호출을 부르는 시간) + O(n) 이다.

그러면 수학적 계산(점화식)으로 시간복잡도를 구해보자

시간 복잡도는 O(nlogn) 이다.

4. 동적계획법(dp)

• 부분 배열의 오른쪽 끝이 A[k] 인 최대 부분 배열의 원소의 합을 S[k] 라고 하자

• 그러면 최대부분배열 원소합은 S[0], S[1], ... , S[n-1] 중 하나일 것이다.

               S[k] = max{S[k-1] + A[k], 0}

위 식을 증명해보자

오른쪽 끝이 A[k]인 최대 부분배열의 길이는 0이거나 1이상일 것이다.

길이가 0인 경우,  S[k] = 0

길이가 1이상인 경우, 

S[k]에서 원소 A[k](오른쪽 끝에있는 원소)를 제거하면 오른쪽 끝이 A[k-1]인 최대 부분배열이 된다.  

<코드>

int MaxSubarray4(int A[], int N)
{
	int MaxSum, ThisSum;
	int k;
	MaxSum = 0;
	ThisSum = 0;
	for (k = 0; k < n; k++) {
		ThisSum = max(ThisSum + A[k], 0);
		MaxSum = max(MaxSum, ThisSum);
	}
	return MaxSum;
}

- 시간복잡도 구하기

어렵지 않게 시간복잡도는 O(n)이라는 사실을 알 수있다.