처음으로 소개할 알고리즘은 Kadane Algorithm 이다.
Maximum Subarray Problem 을 푸는 방법중에 하나의 알고리즘이다. 실제로 해당 문제는 Brute-force 로도 풀 수 있고, Divide & Conquer 로도 풀 수 있지만 카데인 알고리즘이 제일 빠르고 공간 사용도 적기 때문이다.
이 알고리즘에 대한 문제를 Leetcode 에서 풀어보고 싶다면 아래 링크를 참고하길 바란다.
https://leetcode.com/problems/maximum-subarray/
Maximum Subarray - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
카데인을 왜 알아야 하냐면, 위 문제의 출제빈도 및 회사를 확인해보면 알 수 있다.
우선 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$가 $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*(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$번 인덱스까지의 부분합) 를 기준으로 배열의 $4$번째 인덱스의 값을 쭉 더해주면 그게 바로 $4$번 인덱스까지의 부분합이 된다는 것이다.
즉, $n$ 번째 인덱스까지의 부분합은 배열의 $n$ 번째 값과 $n - 1$ 번째 인덱스까지의 부분합에 배열의 $n$ 번째 값을 더한 값을 비교해서 큰 것을 선택하면 그게 최대 부분합이 된다는 것이다.
결국 점화식은 다음과 같다.
$$ \mbox{maxValue[}i\mbox{]} = \begin{cases} \mbox{nums[}0\mbox{]}, & i\mbox{ = 0} \\ \mbox{max(nums[}i\mbox{], nums[}i\mbox{] + maxValue[}i \mbox{ - 1]),} & i\mbox{ > 0} \end{cases} $$
이렇게 구한 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 를 무조건 물어본다는 얘기이다. 말인즉슨, 두가지 방식 모두 할 줄 알아야 한다는 것이다. 해당 풀이법은 향후에 다른 포스팅으로 찾아오겠다.
