소개
1차원 배열이 주어졌을 때, 연속된 구간의 최대 합을 구하는 알고리즘을 카데인 알고리즘이라고 한다.
예를 들어 다음 배열이 있다면,
[-2, 1, -3, 4, -1, 2, 1, -5, 4]연속된 구간 [4, -1, 2, 1]의 합인 6이 가장 크다.
카데인 알고리즘은 앞에서 계산한 결과를 재활용하여 배열을 한 번만 순회한다. 따라서 시간 복잡도 O(n), 공간 복잡도 O(1)로 문제를 해결할 수 있다.
아이디어
현재 원소에서 끝나는 연속 구간의 최대 합을 유지하고 다음 원소를 만났을 때 기존 구간을 이어가는 것과 현재 원소부터 새로운 구간을 시작하는 것 중 더 큰 값을 선택한다.
부분합과 투 포인터를 이용한 접근이 왜 충분하지 않은지 먼저 살펴보면 이 아이디어를 이해하기 쉽다.
부분합을 이용한 풀이
연속된 구간의 합을 구할 때는 부분합 배열을 활용할 수 있다. 먼저 prefix[i]를 배열의 처음부터 i번째 원소까지의 합으로 정의한다.
arr: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
prefix: [ 0, -2, -1, -4, 0, -1, 1, 2, -3, 1]구간 [left, right]의 합은 prefix[right + 1] - prefix[left]로 구할 수 있다. 하지만 모든 시작점과 끝점의 조합을 확인해야 하므로, 최대 구간 합을 찾으려면 여전히 O(n²)개의 구간을 확인해야 한다.
부분합은 특정 구간의 합을 빠르게 구하는 데는 유용하지만, 최대 구간 자체를 찾아야 하는 문제에서는 더 효율적인 방법이 필요하다.
투 포인터의 한계
투 포인터도 배열을 한 번 순회하는 방식처럼 보인다. 하지만 투 포인터를 적용하려면 현재 구간의 상태를 보고 왼쪽 또는 오른쪽 포인터를 이동할 수 있는 기준이 필요하다.
이 문제에서는 그런 기준을 세우기 어렵다. 배열에 음수가 포함될 수 있기 때문에 오른쪽 원소를 추가한다고 해서 합이 항상 커지는 것도 아니고, 현재 합이 작다고 해서 왼쪽 원소를 제거하는 것이 항상 유리한 것도 아니다.
따라서 일반적인 투 포인터 방식으로는 모든 경우를 놓치지 않고 최대 합을 구할 수 없다.
알고리즘
Kadane’s Algorithm
현재 원소를 마지막 원소로 포함하는 연속 구간 중 최대 합을 current라고 하자. 다음 원소 element를 만났을 때 선택지는 두 가지다.
- 기존 구간에
element를 이어 붙인다. - 기존 구간을 버리고
element부터 새로운 구간을 시작한다.
따라서 점화식은 다음과 같다.
current = max(element, current + element)
best = max(best, current)current는 현재 위치에서 끝나는 구간의 최대 합이고, best는 지금까지 확인한 모든 구간 중 최대 합이다.
예시
다음 배열을 순회해보자.
[-2, 1, -3, 4, -1, 2, 1, -5, 4]| 원소 | current | best | 선택한 구간 |
|---|---|---|---|
| -2 | -2 | -2 | [-2] |
| 1 | 1 | 1 | [1] |
| -3 | -2 | 1 | [1, -3] |
| 4 | 4 | 4 | [4] |
| -1 | 3 | 4 | [4, -1] |
| 2 | 5 | 5 | [4, -1, 2] |
| 1 | 6 | 6 | [4, -1, 2, 1] |
| -5 | 1 | 6 | [4, -1, 2, 1, -5] |
| 4 | 5 | 6 | [4, -1, 2, 1, -5, 4] |
4를 만났을 때 이전까지의 합은 음수이므로, 이전 구간을 이어가는 대신 4에서 새로운 구간을 시작한다. 이후 -1, 2, 1을 이어 붙이며 최대 합 6을 얻는다.
동작 원리
카데인 알고리즘은 각 위치에서 끝나는 최대 구간 합만 유지한다. 더 이전의 구간을 모두 저장할 필요는 없다.
- 이전 구간에 현재 원소를 더한 값보다 현재 원소 자체가 크다면 새로운 구간을 시작한다.
- 그렇지 않다면 기존 구간을 이어간다.
- 각 위치에서 계산한
current중 가장 큰 값을best로 유지한다.
이처럼 이전 계산 결과 중 다음 계산에 필요한 값만 남기는 방식이므로, 동적 계획법의 공간을 최적화한 형태로 볼 수 있다.
특징
장점
- 배열을 한 번만 순회하므로 빠르다.
- 추가 배열 없이 최대 구간 합만 구할 수 있다.
- 음수가 포함된 배열도 처리할 수 있다.
단점
- 최대 합만 구하며, 실제 구간의 시작·끝 인덱스는 별도로 추적해야 한다.
- 연속되지 않은 원소를 선택하는 최대 부분 수열 문제에는 사용할 수 없다.
시간/공간 복잡도
배열의 원소 개수를 n이라고 하면 다음과 같다.
- 시간 복잡도:
O(n) - 공간 복잡도:
O(1)
배열을 한 번만 순회하고, current와 best 두 값만 저장하기 때문이다.