알고리즘 Chapter3. Divide and Conquer

분할정복 정리

분할정복 일반적 형태

단, min은 divide 되지 않기 위한 최대 조건

Untitled

$T(n) = \sum_{i=1}^{b} T(n_i) + f(n)$
대부분 $n_1, n_2, \cdots, n_b$ 는 같게 놓으므로 $n_1 = n_2 = \cdots = n_b = \frac{n}{b}$

$\therefore T(n) = a \cdot T(\frac{n}{b}) + f(n)$
위 수식은 $f(n)$에 따라 다르게 풀림

ex :

Untitled

→ 풀이방법 : $O(n^3), O(n^2), O(nlogn), O(n)$

$O(n^3)$ 방법 : 중복조합 ${n}H{2}$ (서로 다른 n개에서 중복을 허용하여 r개를 선택함)
$O(n^2)$ 방법 : 중복조합 ${n}H{2}$ 사용 → 이전에 구했던 합을 재활용
$O(nlogn)$ 방법 : Divide & Conquer
$O(n)$ 방법 : 최대 부분합 수열의 성질 이용

1) $O(n^3)$

Untitled

#include <iostream>
using namespace std;

int maxSubSum1(int* A, int n){
	int max = 0;
	for(int i = 0; i<n; i++){
		for(int j = i; j<n; j++){
			int sum = 0;
			for(int k = i; k<=j; k++){
				sum = sum + A[k];
			}
			if(sum > max){
				max = sum;
			}
		}
	}
	return max;
}

int main() {
  int A[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
  int size = sizeof(A)/sizeof(A[0]);
  int max = maxSubSum1(A, size);
  cout<<max<<endl;
}
/* 출력결과
43 */

2) $O(n^2)$

$O(n^3)$ 방법에서 sum을 저장하여 사용

Untitled