O(n²)에서 O(n)으로: 카데인 알고리즘으로 시간 복잡도 개선하기

김승철·2025년 9월 9일

JavaScript

javascript 정주행

목록 보기

3/8

https://ko.javascript.info/array#tasks 최대합 부분 배열

문제: 최대 부분 배열의 합

알고리즘 문제를 풀다 보면 자주 만나는 고전적인 문제가 있습니다. 바로 '정수 배열이 주어졌을 때, 연속된 부분 배열의 합 중 가장 큰 값을 구하라'는 문제입니다.

예를 들어, [1, -2, 3, 4, -9, 6] 이라는 배열이 있다면, 정답은 [3, 4] 구간의 합인 7입니다.

1. 가장 직관적인 O(n²) 접근법

이 문제를 처음 접했을 때, 가장 먼저 떠오르는 방법은 모든 가능한 부분 배열을 다 확인해보는 것입니다.

배열의 첫 번째 요소부터 마지막 요소까지, 모든 시작점(i)을 정합니다.
각 시작점(i)에서부터 배열의 끝까지 모든 끝점(j)을 정합니다.
i부터 j까지의 합을 구해, 현재까지의 최대값과 비교하여 더 크면 업데이트합니다.

코드:

    function getMaxSubSum_On2(arr) {
      let maxSum = 0;

      for (let i = 0; i < arr.length; i++) {
        let currentSum = 0;
        for (let j = i; j < arr.length; j++) {
          currentSum += arr[j];
          maxSum = Math.max(maxSum, currentSum);
        }
      }

      return maxSum;
    }

이 코드는 정확하지만, for문이 중첩되어 있어 시간 복잡도가 O(n²)입니다. 배열의 크기가 커지면 성능이 급격히 저하되는 문제가 있죠.

2. 발상의 전환: 카데인 알고리즘(Kadane's Algorithm)

이 문제를 O(n), 즉 배열을 단 한 번만 순회해서 풀 수 있는 놀라운 방법이 바로 카데인 알고리즘입니다.

핵심 아이디어:

현재까지 더해온 부분 합(currentSum)이 음수가 되면, 그 구간은 미래에 어떤 값을 더하든 손해만 끼칠 뿐이다. 그러니 과감히 버리고(0으로 리셋), 다음 숫자부터 새로운 부분 배열을 시작한다.

이 '손절'의 아이디어가 카데인 알고리즘의 모든 것입니다.

3. 알고리즘 따라가기

arr = [1, -2, 3, 4, -9, 6] 예제로 알고리즘을 따라가 봅시다.

현재 숫자	`currentSum` 계산	`currentSum`이 음수인가? (음수면 0으로)	`maxSum` 업데이트 (max(maxSum, currentSum))
1	`0 + 1 = 1`	아니오	`max(0, 1) = 1`
-2	`1 + (-2) = -1`	예 -> `currentSum`을 0으로 리셋	`max(1, -1) = 1`
3	`0 + 3 = 3`	아니오	`max(1, 3) = 3`
4	`3 + 4 = 7`	아니오	`max(3, 7) = 7`
-9	`7 + (-9) = -2`	예 -> `currentSum`을 0으로 리셋	`max(7, -2) = 7`
6	`0 + 6 = 6`	아니오	`max(7, 6) = 7`

최종적으로 maxSum은 7이 됩니다.

4. O(n) 코드

이 로직을 코드로 구현하면 for문 하나로 아주 깔끔하게 완성됩니다.

    function getMaxSubSum_On(arr) {
      let maxSum = 0;
      let currentSum = 0;

      for (let num of arr) {
        currentSum += num; // 현재 숫자를 더함

        if (currentSum > maxSum) {
          maxSum = currentSum; // 최대값 업데이트
        }

        if (currentSum < 0) {
          currentSum = 0; // 손해 보는 구간은 버림
        }
      }

      return maxSum;
    }