요즘 Leetcoding 30일 챌린지를 하면서 알고리즘 연습을 하고있던 중
최대 부분합 문제를 풀게 되었는데 아직 알고리즘에 지식이 얕아서 (문제는 해결했지만)
효율성에 있어서 매우 떨어지는 알고리즘만 작성하게 되더라 ㅠㅠ
그래서 오늘은 최대부분합 문제에서 사용하는 카데인 알고리즘에 대해 공부하고 작성하려고 한다.
해당 문제를 보고 오면 더욱 이해가 쉬울거라 생각한다.
문제보기
카데인 알고리즘 (Kadane's Algorithm)
최대부분합
어떤 숫자의 배열이 주어졌을 때 (집합과 달리 각 원소의 자리나 순서를 바꿀 수 없습니다), 연속한 숫자들로 이루어진 부분 배열 중 합이 최대가 되는 경우를 구하는 문제입니다.
예를 들어 [-2, 1, -3, 4, -1, 2, 1, -5, 4]의 배열이 주어졌다면 [4, -1, 2, 1]의 연속한 네 원소로 이루어진 연속 부분 배열의 경우에 합이 6으로 최대가 됩니다.
처음 이 문제를 보았을 때 단순무식하게 이중 for문을 돌려 O(n2)이 걸리는 알고리즘을 작성하였는데 문제 마지막 줄에 O(n)의 효율로도 생각해보라는 문구가 있어서 구글링에 검색하게 됐다.
내가 처음 접근했던 방식과 카데인 알고리즘의 접근 방식을 비교해보자
내가 처음 접근했던 방식
주어진 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]
sum{-2}, sum{-2,1}, sum{-2,1,3} ... sum{-2, 1, -3, 4, -1, 2, 1, -5, 4}
sum{1}, sum{1,-3} ... sum{1, -3, 4, -1, 2, 1, -5, 4}
...
sum{4}
카데인 알고리즘으로 접근한 방식
주어진 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]
sum{-2}
sum{-2,1}, sum{1}
sum{-2,1,-3}, sum{1,-3}, sum{-3}
sum{-2,1,-3,4}, sum{1,-3,4}, sum{-3,4}, sum{4}
...
내가 처음 접근한 방식은 배열의 i번째 인덱스부터 시작하여 각 부분배열의 합을 더한 후 최댓값을 반환하는 방식이다. 근데 이렇게 접근해버리면 처음 부터 끝까지 부분배열의 합을 계산해야 하니 효율성에서 뒤떨어지는 방식이다.
카데인 알고리즘은 배열의 i번째 인덱스를 끝을 기준으로 잡는다. 그렇게 되면
i+1번째 원소에서 부분배열의 합들의 최댓값은 i번째 부분배열에 i+1번째 원소를 더한 값과 i+1번째 원소를 비교한 최댓값이 결과로 나오게 된다.
이게 무슨 소린가 하면
- i=0일 때 sum{-2} 최댓값은 -2
- i=1일 때 sum{-2,1} = -1, sum{1} = 1
즉 i=1일 때의 부분집합 sum{-2,1}은 i=0일 때의 부분집합에 i+1번째 원소를 더한것과 sum{1}을 비교하여 최댓값 1을 반환 - i=2일 때 sum{-2,1,-3}, sum{1,-3}, sum{-3}중 최댓값을 찾아야 하는데 이미 i=1일때의 최댓값을 우리는 알고있다.
sum{-2,1} -3 (i+1의 원소) < sum{1} -3 (i+1의 원소) 이 더 큰걸 알고있으니 sum{1,-3}과 sum{-3}만 비교하면 되는 것이다.
이렇게 배열의 끝까지 n번만 순회하면 부분집합의 최댓값을 찾을 수 있어서 O(n)의 시간복잡도를 가지게 된다!
코드
public static int maxSubArray2(int[] nums) {
int maxSum = 0;
int endMax = Integer.MIN_VALUE;
for (int i = -1; i < nums.length - 1; i++) {
maxSum = Math.max(maxSum + nums[i + 1], nums[i + 1]);
endMax = Math.max(maxSum, endMax);
}
return endMax;
}마침
처음으로 블로그에 알고리즘을 글로 작성하려고 보니 너무 어렵다....
솔직히 글을 쓰면서도 이해가 잘 안돼서 계속 찾아봤다 ㅠㅠ
게다가 글 쓰는 재주도 없으니 다른 분들이 봤을 때 이해를 잘 할 수 있을까라는 걱정도 든다...
점점 쓰다 보면 나아지겠지 ㅠㅠ
참고
