[DynamicProgramming] Kadane's Algorithm(카데인 알고리즘)

카데인 알고리즘에 대해 알아봅니다.

 

 

 

1. 앞선 글

 

널리 알려진 알고리즘 문제 중에 "Maximum Subarray"라는 문제가 있습니다. 간단히 설명하자면 주어진 배열에서 연속되는 숫자의 합 중 가장 큰 합을 구하는 문제입니다.

 

보통 이 문제를 해결하면서 가장 먼저 시도하는 방법은 모든 경우의 수를 다 구해보는 Brute Force일 겁니다. 문제는 배열의 수가 커지면 커질수록 이 방법은 Timeout이 발생할 확률이 매우 높아진다는 것입니다.

 

이제 다음으로 드는 생각은 DynamicProgramming을 이용해보자 일 겁니다. 보통 이런 Maximum Subarray와 관련된 문제는 연관 테마가 DynamicProgramming이기도 하니까요. 이때 적용되는 알고리즘이 바로 카데인 알고리즘입니다.

 

 

 

2. 카데인 알고리즘

 

우선 모든 경우의 수를 다 계산하는 Brute Force 접근법을 생각해 봅시다. 단, 이번에는 거꾸로 한번 생각해보도록 합니다. 즉, 배열 A의 크기가 n이라 할 때 A[0]이 아닌 A[n-1]부터 말이죠.

 

아래 그림과 같이 마지막부터 시작하여 A[n-1]로 끝나는 가능한 모든 배열의 합을 계산합니다. 그런 다음 A [n-2], A [n-3] 등으로 끝나는 가능한 모든 하위 배열의 합을 A[0]까지 계산합니다.

 

 

이제 하나를 직접 찍어서 생각해 봅시다. 아래 그림에 표시된 A[4](=-1) 및 A[5](=2)로 끝나는 배열에 초점을 맞추겠습니다.

 

 

위 그림에서 A[4]로 끝나는 배열의 최대 합은 [4, -1]의 합인 3입니다. 이제 A[5]로 끝나는 배열을 살펴 봅시다. A[5]로 끝나는 배열은 노란색으로 강조된 A[4]로 끝나는 배열과 녹색으로 강조된 단일값 A[5]로 구성됨을 확인할 수 있습니다.

 

이제 우리는 A[4]로 끝나는 배열의 합을 알고 있다면 A[5]로 끝나는 배열의 합을 구하기 위해 모든 값을 다시 계산할 필요가 없다는 것을 알게 되었습니다. 이것이 카데인 알고리즘의 원리입니다.

 

즉 카데인 알고리즘을 한 문장으로 표현하자면 다음과 같습니다.

 

배열 A에서 인덱스 i까지의 최대 합은 인덱스 i-1까지의 최대 합과 A[i]의 값을 더한 값입니다. 

MaxSum[i] = Max( A[i], A[i] + MaxSum[i-1] )

 

이런 식으로 모든 인덱스 i에서의 값을 구하는 것은 A[i]와 A[i] + [i-1]까지의 최대 합인 두 숫자를 찾는 것으로 줄일 수 있습니다. 그러므로 재귀 함수를 사용한다면 간단히 해결할 수 있으며 Brute Force 보다 훨씬 낫습니다. 실제로 카데인 알고리즘의 시간 복잡도는 O(n)입니다.

 

 

 

3. 코드에 적용: JavaScript

 

위의 내용을 직접 코드에 반영해본다면 다음과 같이 나타낼 수 있습니다.

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let curSum = nums[0];
    let maxSum = nums[0];
    
    for(let i = 1; i < nums.length; i++) {
    	curSum = Math.max(nums[i], curSum + nums[i]);
        if(curSum > maxSum) {
        	maxSum = curSum;
        }
    }
    
    return maxSum;
};

 

 

 

 

 

References

Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?