[알고리즘] 카데인 알고리즘(DP)

굉장히 일반적이고 평범한 DP문제에서 공간복잡도와 시간복잡도를 간단한 논리로 줄일 수 있는 알고리즘이다.

생각보다 이해하기 쉽다.

추후에 자연스럽게 떠올릴 수 있도록 체화시키는게 시간이 좀 걸릴뿐.

일단 해당 알고리즘을 사용해야 풀리는 가장 쉬운 문제가 이 문제임

https://www.acmicpc.net/problem/2670

2670번: 연속부분최대곱

 

---

이 문제를 보면 가장 먼저 떠오르는 방식은 브루트포스로 처리하는 것이다.
 
무식하게 다음과 같이 짤 수도 있고
 

	for (int i = 1; i <= N; i++) {
		double sum = 1;
		for (int k = i; k <= N; k++) {
			sum *= arr[k];

			if (sum > maxsum) {
				maxsum = sum;
			}
		}
	}

 
DP로 푼다는 것을 생각해 다음과 같이 짤 수 도 있다.
 

#include <iostream>
#include <cstdio>
#define SIZE 10001

using namespace std;

double dp[SIZE][SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	double max = 0;
	int N; cin >> N;
	for (int i = 1; i <= N; i++) { cin >> dp[i][i]; }

	for (int x = 2; x <= N; x++) {
		for (int y = x - 1; y >= 1; y--) {
			dp[y][x] = dp[y][x - 1] * dp[x][x];
			if (dp[y][x] > max) {
				max = dp[y][x];
			}
		}
	}

	printf("%.3lf", max);
	return 0;
}

 
하지만 이 둘은 모두 O(N^2)이다.
심지어 두번째 코드는 dp를 사용하기 위해 dp[SIZE][SIZE]를 사용하고 심지어 이때 이 중 절반은 사용하지도 않는다.
 그래서 공간복잡도도 N^2이 된다.

 

그래서 두번째 코드로 하면 메모리초과로 틀렸다고 뜬다.
 
double(8Byte) *  100,000,000 > 128M > 100,000,000 byte 니까 (당연히 float로 해도 틀림)
 
이럴때 시간복잡도와 공간복잡도가 모두 O(N)인 카데인 알고리즘을 쓰면 된다.
 

---

배열을 딱 한번만 뒤짐
dp용으로 쓸 1차원 배열 하나 + 정수형 변수 2개로 풀 수 있다.
 
논리는 
만약 전 것들의 곱이 1 미만이면 당연히 이번꺼랑 곱하면 이번 차례의 수보다 작아질 것이다.
따라서 이때 끊어주는 것이다.
 

#include <iostream>
#include <cstdio>
#define SIZE 10001

using namespace std;

double arr[SIZE], dp[SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int N; cin >> N;
	for (int i = 1; i <= N; i++) { cin >> arr[i]; }

	int maxidx = 0;
	double sum = 1;

	for (int i = 1; i <= N; i++) {
		// 1보다 작으면 무조건 숫자가 작아지니 
		// 합을 초기화하고 다시 시작
		if (dp[i - 1]< 1) {
			sum = 1;
		}

		sum *= arr[i];
		dp[i] = sum;

		// 매번 최신화
		if (dp[i] > dp[maxidx]) maxidx = i;
	}

	printf("%.3lf", dp[maxidx]);
	return 0;
}

 

---

이거의 다른 유형으로는 연속부분합이 있다.
 
논리는 똑같다.
 
전 숫자들의 합이 음수이면 당연히 이번 수랑 합하면 전체합은 작아질 수 밖에 없다.
따라서 전 숫자들의 합이 음수이면 위처럼 한번 끊어주고 다시 0부터 시작한다.
 

int maxSubArraySum(int* arr, int n) {
	int maxSumSoFar = 0;
	int maxSumEndingHere = 0;

	for (int i=0; i < n; i++) {
		maxSumEndingHere += arr[i];

		// 만약 음수면 다음꺼부터 새로 시작
		if (maxSumEndingHere < 0) {
			maxSumEndingHere = 0;
		}

		// 더한값이 음수도 아니고 최고보다 크면 갱신
		if (maxSumSoFar < maxSumEndingHere) {
			maxSumEndingHere = maxSumSoFar;
		}
	}
	return maxSumSoFar;
}