카데인 알고리즘

DP (Dynamic Programming) 기법 중 하나로서, 각 수들을 더했을 때 가장 큰 수가 나오는 연속된 부분을 찾는 알고리즘 ( 시간복잡도: O(n) )

local_max[i] = max(A[i] + local_max[i-1], A[i])

많은 분들이 Maximum Subarray Problem 문제 해결방법을 알아보다 카데인 알고리즘을 알게되었을텐데, Maximum Subarray Problem을 통해 카데인 알고리즘을 알아보겠습니다.

Maximum Subarray Problem (최대 부분 합 구하기)

최대 부분 합 구하기 문제는 주어진 1차원 배열의 부분 배열에서 최대 합을 가지는 값을 구하는 문제입니다.

A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

위 배열에서 가장 큰 합을 가지는 부분 배열은 [4, -1, 2, 1]이며, 최대 합은 6이 됩니다.

저를 포함하여 대다수가 Brute Force로 접근했을텐데 Brute Force를 간단하게 알아보겠습니다.

인덱스 0부터 N-1까지 모든 부분 배열의 합을 구한 뒤, 부분 배열의 합 중 가장 큰 값을 찾는 방식

A[0]부터 A[0..1], A[0..2], A[0..N-1]까지 모든 부분 합을 구한다.
Sum 배열에 등록된 A[0]의 모든 부분 합 중, 가장 큰 부분 합(local_max)을 구한다.
1,2 를 반복한다.
(A[1]부터 A[1..2], A[1..N-1]까지 local_max 구하고, A[2]에서 local_max 구함을 반복)
0부터 N-1까지 구한 local_max[0...N-1]에서 가장 큰 값(global_max)을 구한다.
global_max를 리턴

위 방법은 배열의 사이즈가 커지는 만큼 1-2번을 반복해야하는 횟수도 커집니다. ( 시간 복잡도: O(n²) )

또한 이미 A[i]에서 구했던 값을 A[i+1]에서 다시 구해야하는 문제가 존재합니다.

그림 맨 왼쪽에 표기된 "1"에서 구한 [-2, 1]의 합인 -1을 "2"에서 [-2, 1, -3]의 합을 구하는 과정에서 이미 구했던 [-2, 1]을 다시 계산하게 됩니다.

배열의 크기가 커질수록 이미 구했던 값을 중복되게 구하는 과정이 많아져, 비효율적임을 알 수 있습니다.

Brute Force에 가장 큰 단점은 이미 구했던 값을 다시 구한다는 점입니다.

카데인 알고리즘은 "이미 구했던 값은 다시 재사용"하는 접근법을 이용하며, Brute Force의 A[0]~A[N-1]의 접근 방법이 아닌 A[N-1]~A[0] 접근 아이디어를 사용합니다.

위 그림을 보면 A[5]의 local_max를 구하려면, A[4]의 local_max + A[5]를 해주면 되는걸 확인할 수 있습니다.

※ 각 A[4] Sum 배열 값에 A[5]를 더해주면 A[5] Sum에 대한 값들이 나옴

이러한 방법은 A[5]의 모든 부분 합을 처음부터 다시 계산하지 않더라고 A[5]에 부분 합을 구할 수 있음을 뜻합니다.

A[N-1]~A[0] 아이디어를 통해 나온 규칙을 기반으로 아래의 카데인 알고리즘 공식을 유추할 수 있고, 이 때 시간복잡도는 O(n)을 가집니다.

local_max[i] = max(A[i] + local_max[i-1], A[i])

위 공식은 부분 집합의 최대 합을 구하는 목적이기 때문에, A[i]+local_max[i-1]과 A[i] 중 무엇이 더 큰지 비교합니다. (A[i]가 더 크다면 이 전에 구했던 부분 집합은 필요 없기 때문)

이렇게 구한 local_max 배열에서 가장 큰 값을 구하면 Maximum Subarray Problem의 최대 부분 배열 합을 구할 수 있습니다.