카데인 알고리즘(Kadane's Algorithm)은 연속된 부분 배열에서 최대 합을 찾는 효율적인 방법이다. 즉, "최대 연속 부분 배열(Maximum Subarray) 문제"를 해결하는 데 사용된다.
1. 문제 정의
주어진 배열에서 연속된 부분 배열 중 합이 최대가 되는 구간을 찾는 문제다. 예를 들어 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 있다고 할 때, 이 배열에서 최대 합을 가지는 연속 부분 배열은 [4, -1, 2, 1]이며, 그 합은 6이다.
2. 직관적인 접근
이 문제를 해결하려면 배열의 모든 부분 배열을 탐색하여 합을 계산하는 방식으로 접근할 수도 있다. 그러나 이런 접근 방식은 O(n^2) 혹은 O(n^3) 시간 복잡도를 가지기 때문에, 입력 크기가 커질수록 매우 비효율적이다.
카데인 알고리즘은 이 문제를 한 번의 순회로 해결할 수 있도록 해주며, 시간 복잡도는 O(n)이다. 다음은 카데인 알고리즘의 원리다.
3. 카데인 알고리즘의 핵심 개념
카데인 알고리즘은 다음과 같은 아이디어를 기반으로 한다.
배열의 각 위치에서 해당 위치를 포함하는 연속된 부분 배열의 최대 합을 계산하고, 그 값들 중에서 전체 최대 합을 찾는다. 현재 위치에서의 최대 부분 배열 합을 갱신하며 이동한다.
4. 단계별 설명
-
초기화:
maxSum 변수는 지금까지 찾은 전체 최대 부분 배열 합을 저장한다.
currentSum 변수는 현재 위치에서 끝나는 최대 부분 배열 합을 저장한다.
처음에는 maxSum과 currentSum을 배열의 첫 번째 원소로 초기화한다. -
배열을 순회:
배열의 두 번째 원소부터 시작해서 끝까지 순회한다.
currentSum을 업데이트할 때, 현재 원소만 포함하는 것이 더 큰지 아니면 이전의 합에 현재 원소를 더하는 것이 더 큰지 판단한다. 이를 통해 최대 부분 배열의 합을 실시간으로 갱신한다.
maxSum은 currentSum이 더 클 경우에 갱신된다. -
수식으로 표현:
currentSum = max(arr[i], currentSum + arr[i])
이 식은 현재 위치의 값 (arr[i])과 이전의 최대 합에 현재 값을 더한 것 (currentSum + arr[i]) 중 더 큰 값을 선택하는 것이다.
maxSum = max(maxSum, currentSum)
maxSum은 현재까지 발견한 최대 구간 합을 유지한다.
5. 예제
배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
maxSum = -2
currentSum = -2
첫 번째 순회 (i = 1, 원소는 1):
currentSum = max(1, -2 + 1) = 1
maxSum = max(-2, 1) = 1
두 번째 순회 (i = 2, 원소는 -3):
currentSum = max(-3, 1 + (-3)) = -2
maxSum = max(1, -2) = 1
세 번째 순회 (i = 3, 원소는 4):
currentSum = max(4, -2 + 4) = 4
maxSum = max(1, 4) = 4
네 번째 순회 (i = 4, 원소는 -1):
currentSum = max(-1, 4 + (-1)) = 3
maxSum = max(4, 3) = 4
이후 같은 방식으로 배열을 끝까지 순회한다.
최종적으로 maxSum은 6이 되며, 이는 [4, -1, 2, 1]이라는 연속 부분 배열의 합이다.
6. 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int maxSum = arr[0];
int currentSum = arr[0];
for (int i = 1; i < n; i++) {
currentSum = max(arr[i], currentSum + arr[i]);
maxSum = max(maxSum, currentSum);
}
cout << "Maximum Subarray Sum: " << maxSum << endl;
return 0;
}currentSum은 배열의 각 요소를 포함하는 최대 부분 배열의 합을 계속 갱신한다.
maxSum은 전체 최대 부분 배열의 합을 유지한다.
7. 결론
카데인 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)이다. 카데인 알고리즘은 배열을 순회하면서, 현재 원소를 포함하는 것이 유리한지, 아니면 새로운 시작점을 만드는 것이 유리한지를 결정한다. 이 과정에서 항상 현재까지의 최적 해를 유지하므로, 단 한 번의 배열 순회를 통해 문제를 해결할 수 있다.
