[Algorithm] Kadane's Algorithm

처음으로 소개할 알고리즘은 Kadane Algorithm 이다.

Maximum Subarray Problem 을 푸는 방법중에 하나의 알고리즘이다. 실제로 해당 문제는 Brute-force 로도 풀 수 있고, Divide & Conquer 로도 풀 수 있지만 카데인 알고리즘이 제일 빠르고 공간 사용도 적기 때문이다.

 

이 알고리즘에 대한 문제를 Leetcode 에서 풀어보고 싶다면 아래 링크를 참고하길 바란다.

https://leetcode.com/problems/maximum-subarray/ 

Maximum Subarray - LeetCode

카데인을 왜 알아야 하냐면, 위 문제의 출제빈도 및 회사를 확인해보면 알 수 있다.

 

그냥 어마어마하다...

 

 

우선 Maximum Subarray Problem 에 대해서 설명을 해야한다.

아래와 같은 정수형 배열이 주어지고, 연속하는 부분배열의 합 중 가장 큰 것을 구하라는 문제이다. (중복가능)

 

 

위와 같이 주어진 경우에 직관적으로 구해보면, 아래와 같이 $1$번 인덱스에서 $4$번 인덱스까지 더했을때 $7$로 가장 큰 합이 나오는 것을 알 수 있다.

우선 Brute-force 로 어떻게 구하는지부터 확인해보겠다.

한번의 반복을 통해 처음 인덱스 $start$를 구하고 나머지 구간에서의 반복을 통해 마지막 인덱스 $end$를 구하는 방식으로 풀면 된다. 그리고 localMaxValue 를 추가해서 현재 구간합을 저장해준다. globalMaxValue 를 선언해서 부분배열의 합들과 비교해서 작은 경우에 변경해준다. (maxValue 를 비교하려고 하는 경우에는 Integer.MIN_VALUE 로 초기화해주는 것이 좋다.)

위에서 주어진 배열에 인덱스를 추가해서 확인해보겠다.

첫번째 반복문이 돌면서 $start$는 $0$번 인덱스를 취할 것이다. 그리고 두번째 반복문에서 $end$를 찾기 위해서 $0$번부터 $1$씩 증가하면서 값들을 더해준다.

아래 표는 ($start$, $end$) 가 ($0$, $0$) ~ ($0$, $2$) 까지 반복되는 과정을 보인다.

start 가 0 일때 end 가 0 ~ 6까지 반복되는 경우

$start$ 는 $0$이고 $end$가 $6$이 될때까지 반복이 쭉 이어지면서 각각의 부분배열의 부분합이 구해지고 그걸 globalMaxValue 와 비교하면서 부분합이 큰 경우에 globalMaxValue 에 할당해주면 된다.

그래서 $start$가 $0$인 경우에 부분합은 $[-3,-1,-2,2,4,-1,2]$ 의 순서대로 구해지므로, globalMaxValue 는 $[-3,-1,-1,2,4,4,4]$ 로 변경된다.

두번째 반복문이 끝이 났으므로 첫번째 반복문의 $start$ 가 $1$ 인 경우를 살펴보겠다. (그리기 귀찮으므로 그림은 생략한다.), 

$start$ 가 $1$이고 $end$가 $6$이 될때까지 반복을 하면서 부분합을 구해준다. $[2,1,5,7,2,5]$ 의 순서대로 구해지므로, globalMaxValue 는 $[4,4,5,7,7,7]$ 로 변경된다. 

마찬가지로 $start$ 가 $2$로 증가되고, $3$으로 증가되면서 $6$까지 증가되면서 $end$를 구해주면 종료된다.

반복문은 $(7+6+5+4+3+2+1)$ 회 만큼 발생하므로, $\frac{n\ast (n+1)}{2}$ 의 시간복잡도를 가질 것이다. ☞ $O(n^2)$

공간복잡도는 $int$형 변수만 사용했으니 $O(1)$ 이라고 볼 수 있다.

 

이런 경우에 $n$ 이 10만을 넘으면 흔한 프로그래밍 툴에서는 Time Limit Exceeded (a.k.a TLE) 를 맛볼 것이다.

Leetcode 에선 이런 것이 좀 관대한 편인데, 사실 좋은 알고리즘은 아니니 최대한 줄이려고 하는 노력이 필요하다.

 

그래서 오늘 소개하려는 Kadane 알고리즘을 사용하는 것이 좋다.

One-pass 에 종료할 수 있고, Dynamic Programming 개념의 기초를 잡기에 딱 좋은 알고리즘이다.

다들 DP 가 결국 점화식을 구하면 된다는 것은 잘 알고 있을 것이다.

여기서의 점화식을 구하기 위해서 배열의 $n-1$ 번째와 $n$ 번째의 관계를 살펴보자.

위에서는 인덱스의 처음부터 달려나갔다면, 이번에는 약간의 역발상으로 $n$에서 돌아간다고 생각하는 것이다.

$n$ 과 $n+1$ 도 가능하지만, 그런 경우에는 $n+1$ 의 점화식을 구하게 되는 것이라 $n$ 과 $n-1$ 을 기준으로 한다.

 

3번째 인덱스까지의 최대 부분합은 5이고, 4번째 인덱스까지의 최대 부분합은 7

 

위의 그림에서 규칙을 찾을 수 있는데, 왼쪽 표 ($3$번 인덱스까지의 부분합) 를 기준으로 배열의 $4$번째 인덱스의 값을 쭉 더해주면 그게 바로 $4$번 인덱스까지의 부분합이 된다는 것이다.

즉, $n$ 번째 인덱스까지의 부분합은 배열의 $n$ 번째 값과 $n-1$ 번째 인덱스까지의 부분합에 배열의 $n$ 번째 값을 더한 값을 비교해서 큰 것을 선택하면 그게 최대 부분합이 된다는 것이다.

 

결국 점화식은 다음과 같다.

$$\text{maxValue[}i\text{]}=\{\begin{array}{ll}\text{nums[}0\text{]},& i\text{ = 0}\\ \text{max(nums[}i\text{], nums[}i\text{] + maxValue[}i\text{ - 1]),}& i\text{ > 0}\end{array}$$

 

이렇게 구한 maxValue 는 최종리턴할 결과물이 아니라 각 인덱스별 부분합이라고 볼 수 있다.

즉, 최종적인 최대값을 두어서 비교해주면 끝이 난다.

코드를 확인해보자.

class Solution {
    public int maxSubArray(int[] nums) {
        int globalMaxValue = nums[0]; // 최종적으로 리턴할 변수
        int localMaxValue = nums[0]; // 인덱스별로 구한 부분합
        for (int i = 1; i < nums.length; i++) { // 0번 인덱스는 포함되어 있으니 1번부터 마지막까지 돌려줌
            localMaxValue = Math.max(nums[i], nums[i] + localMaxValue); // 나 자신과 이전까지 최대값을 더해서 비교해주면 현재까지의 최대값이 나옴
            globalMaxValue = Math.max(globalMaxValue, localMaxValue); // 리턴할 값과 비교해줌
        }
        
        return globalMaxValue;
    }
}

코드 자체가 간단하고, 알고리즘을 이해하기 어렵지 않기 때문에 쉽게 넘어가는 경우가 많은데 잘 이해하지 못하면 나중에 다시 어버버 할 수도 있으니 꼭 이해하고 넘어가길 바란다. (저한테 하는 소리입니다...)

 

그리고 이 포스팅에서는 Divide & Conquer 방식은 설명하지 않았지만, Leetcode 에서 follow-up 이 달려있는 것으로 봐서는 카데인으로 풀어도 D&C 를 무조건 물어본다는 얘기이다. 말인즉슨, 두가지 방식 모두 할 줄 알아야 한다는 것이다. 해당 풀이법은 향후에 다른 포스팅으로 찾아오겠다.

 

Leetcode 의 Follow-up 은 무조건 다른 풀이법이 있다는 뜻이니, follow-up 문제의 경우 2개의 풀이법은 필수