카데인 알고리즘(DP)

DP(Dynamic Programing)

카데인 알고리즘을 설명하기 전에 DP를 알아야 한다.
다이나믹 프로그래밍은 이름과는 전혀 상관없는 알고리즘이다.
DP는 복잡하게 반복해야 하는 문제를 나누고
그 값들을 저장해 두었다가 재사용하는 알고리즘이다.

DP를 아이들도 이해할 수 있게 설명한 방법이 있다.(출처)
1+1+1+1+1+1+1+1 이란 것을 아이에게 보여주고 답을 물어보면
아이는 1을 세어보고 8이라고 대답할 것이다.
그럼 이제 +1을 추가로 써서 다시 답을 물어보면 이번에는 매우 빠르게 9라고 답할 것이다.
어떻게 9인지 바로 알았냐고 물어보면 아이는 그냥 1을 더했다고 말할 것이다.
왜냐하면 이미 8이라는 수를 기억해 두었다가 1을 더한 것이다.
그래서 다시 1의 개수를 셀 필요가 없었다.

카데인 알고리즘

카데인 알고리즘은 최대 부분 합을 구할 때 유용하다.
예를 들어 6개의 수열 -3 4 9 -2 -5 8이 있을 때
합이 가장 최대인 구간을 구한다면 2~6번째 수를 더한 14이다.

이런식으로 생각을 해보자
4번째 수까지 합을 계산해보면 위의 표와 같다.

5번째 수까지 합을 구하면 이렇게 나온다.

눈치채기 힘들 수도 있지만 위 방법에는 규칙이 있다.
4번째 수까지의 합에서 5번째로 넘어가는 것을 살펴보면

위와 같이 4번째 수까지의 합에서 5번째 수를 더한 값과 같아진다.

그러므로 4번째 수까지의 최대 부분합을 안다면 5번째 수까지의 최대 부분합을 구하는건 쉬운 것이다.
이를 코드로 표현해보면

1

maxNumber[i] = max(number[i], number[i] + maxNumber[i-1]);

이런식으로 나타낼 수 있다.

예시 문제

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

문제풀이

설명한 카데인 알고리즘을 그대로 구현하면 된다.
다만 위의 코드에서는 배열에다가 n번째의 최대 부분합을 저장했지만
이 문제에서는 그럴필요 없이 전체의 최대 부분합 하나만 구하면 되기 때문에
배열 대신 변수 하나를 이용해 최대 부분합을 구해주었다.

전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<iostream>
#include<algorithm>
#include<vector>
#include<limits.h>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	while (true) {
		int n; cin >> n;
		if (n == 0) break;
		ll sum = 0, res = LLONG_MIN;
		for (int i = 0; i < n; i++) {
			ll x; cin >> x;
			sum += x;
			res = max(res, sum);
			if (sum < 0) sum = 0;
		}
		cout << res << "\n";
	}
	return 0;
}