[Algotithm] Kadane’s Algorithm

오늘은 Kadane’s Algorithm에 대해 공부해봅시다.

Kadane’s Algorithm은 Maximum Sum Subarray Problem(최대 부분합 문제)을 해결하는 기법으로 유명하며,

Dynamic Programming(DP)의 여러 기법 중 하나입니다.

또한 배열의 요소가 정수 범위라고 가정합니다.

핵심

배열을 순차적으로 순회하면서, 현재까지의 부분합과 최대 부분합을 유지하는 것이 핵심입니다.

처음에는 의미를 한 번에 이해하지 못했는데요.

아래 그림을 봅시다.

출처: https://en.wikipedia.org/wiki/Maximum_subarray_problem

위 그림은 [2, 3, -1, -20, 5, 10]의 최대 부분합을 구하는 과정을 시각화한 그림입니다.

x축은 Index를, y축은 요소들의 합을 나타냅니다. 배열의 길이만큼의 그래프가 그려집니다.

 

그래프를 좀 더 자세히 그려봅시다.

두 개의 그래프를 추가했습니다.

파란색 점선 그래프는 각 인덱스에서의 최대 부분합을 붉은색 점선 그래프는 현재까지의 최대 부분합을 나타냅니다.

각 인덱스에서 새로운 부분합을 만들 때, 이전 부분합에 현재 요소를 더할지, 아니면 새로운 부분합을 시작할지를 결정합니다.

따라서 이전 부분합에 현재 요소를 더한 값과 현재 단일 요소의 값을 비교하고 더 큰 값을 새로운 부분합으로 저장합니다.

왜 DP(Dynamic Programming)인가?

제대로된 원리를 이해하기 위해서 더 높은 카테고리에서 접근해보겠습니다.

[Algorithm] Dynamic Programming(DP; 동적계획법)

DP의 핵심은 문제를 작은 문제로 나누기, Caching 데이터, 점화식, 최소 단위 조건(가장 작은 문제가 무엇인가?)이 있었습니다.

핵심대로 문제에 접근해보면 어떨까요? [2, 3, -1, -20, 5, 10] 예제를 활용하여 접근해봅시다.

[2, 3, -1, -20, 5, 10]
 ^
// 첫 번째 요소
currentMax = 2
totalMax = 2

 

첫 번째 요소는 그대로 활용합니다.

두 번째 요소부터는 새로운 부분 배열을 시작할지 or 기존의 부분배열을 이어갈지를 결정하게 됩니다.

[2, 3, -1, -20, 5, 10]
    ^
기존 배열에 현재 값을 추가했을 경우의 부분 배열	: [2, 3] -> sum = 5
새로 시작할 경우의 부분 배열 : [3] -> sum 3
최대값을 구하기 때문에 두 값 중 더 큰 값을 저장
currentMax = max(5, 3) // 5

전체 최대값(totalMax) : 2
현재의 인덱스에서의 계산 결과(currentMax) : 5
totalMax = max(2, 5) // 5

이 과정을 반복해봅시다.

[2, 3, -1, -20, 5, 10]
        ^
기존 배열에 현재 값을 추가했을 경우의 부분 배열	: [2, 3, -1] -> sum = 4
새로 시작할 경우의 부분 배열 : [-1] -> sum -1
currentMax = max(4, -1) // 4
totalMax = max(5, 4) // 5

[2, 3, -1, -20, 5, 10]
             ^
기존 배열에 현재 값을 추가했을 경우의 부분 배열	: [2, 3, -1, -20] -> sum = -16
새로 시작할 경우의 부분 배열 : [-20] -> sum -20
currentMax = max(-16, -20) // -16
totalMax = max(5, -16) // 5

[2, 3, -1, -20, 5, 10]
                ^
기존 배열에 현재 값을 추가했을 경우의 부분 배열	: [2, 3, -1, -20, 5] -> sum = -11
새로 시작할 경우의 부분 배열 : [5] -> sum 5
currentMax = max(-11, 5) // 5  -> 부분 배열을 새로 만들기 시작!!
totalMax = max(5, 5) // 5

[2, 3, -1, -20, 5, 10]
                    ^
기존 배열에 현재 값을 추가했을 경우의 부분 배열	: [5, 10] -> sum = 15
새로 시작할 경우의 부분 배열 : [10] -> sum 10
currentMax = max(15, 10) // 15
totalMax = max(5, 15) // 15

값 5가 들어오면서 새로운 부분 배열을 만들기 시작합니다. 왜 이런 일이 일어날까요?

값이 연속된 부분 배열이고 최대값을 구해야하는 조건 속에서 특정 인덱스부터의 누적합이 음수의 값을 같는 경우(예시에서의 [2,3,-1,-20]), 해당 구간을 버리고 새로운 부분 배열을 생성하는 것이 최대값을 고려하는 방법이 됩니다.

 

따라서 이전까지의 부분 배열이 음수일 때 무조건 적으로 새로운 부분 배열을 생성하는 방법도 존재합니다.

하지만 그럴 경우 모든 배열이 음수인 경우, 정상적으로 작동하지 않습니다.

 

이처럼 작은 크기의 배열부터 값을 하나씩 확인해가며 문제를 해결하고,

그 과정에서 이전 부분 합과 최대합의 결과를 저장하여 사용하기 때문에 DP의 개념에 맞게 됩니다.

코드

코드로 살펴봅시다.

let arr = [2, 3, -1, -20, 5, 10]
var indexMaxValue = arr.first ?? Int.min
var maxValue = arr.first ?? Int.min

for i in (1..<arr.count) {
    indexMaxValue = max(indexMaxValue + arr[i], arr[i])
    maxValue = max(maxValue, indexMaxValue)
}
print(maxValue)

핵심이 되는 코드는 반복문 안의 코드입니다.

indexMaxValue = max(indexMaxValue + arr[i], arr[i])

각 인덱스에서 이전의 부분 배열을 이어갈지 혹은 부분 배열을 새로 만들지 결정합니다.

maxValue = max(maxValue, indexMaxValue)

결정된 값과 지금까지의 값을 비교하여 큰 값을 저장합니다.

Conclusion

원리 없이 공식만 외우듯, 이전에는 코드는 작성할 수 있지만 작동하는 이유에 대해서는 설명할 수 없었습니다.

개념 정리하고 나니 왠지 속이 조금 후련해진 느낌입니다.