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

buckshot·2025년 3월 2일

알고리즘

목록 보기

15/19

코딩테스트 문제를 풀면서 이런 문제를 보았다.

주어진 배열의 부분 배열과 펄스 수열을 곱의 합 중 가장 큰 수는?

솔직히 카데인 알고리즘에 대한 개념이 없었기 때문에 초기에는 각 시작 인덱스를 기준으로 부분 배열의 경우의 수를 계산하여 결과를 반환했다.

그러면 주어진 배열에서 가능한 모든 경우의 부분배열을 찾아서 계산해야 한다는 불편한 부분이 있었다,

기존에 생각한 방법이 아닌 좀 더 효율적인 방법을 찾아본 결과 Kadane's Algorithm 이라는 것을 알았다.

개념

카데인 알고리즘(Kadane’s Algorithm)은 연속된 부분 배열(Subarray) 중 합이 최대가 되는 값을 효율적으로 해결 가능한 알고리즘이다.

카데인 알고리즘의 핵심은 각 부분의 최대 합을 구할 때는 바로 전 단계의 최대 합을 이용하여 구하는 것이다.

해당 알고리즘은 **O(n)**의 시간 복잡도로 간단하게 해결할 수 있다는 점이 장점이라고 생각한다.

과연 다른 알고리즘 보다 좋은 방법이야? 🤔

정말로 카데인 알고리즘이 다른 알고리즘 보다 효율적인 방법인지 확인을 하자.

1. Kadane’s Algorithm

현재의 부분 배열의 합을 갖고 추가적인 연산을 통하여 최대의 합을 구하고 있다.

public int maxSubarrayKadane(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

아래의 코드를 보면 현재 인덱스의 값과 현재의 합을 비교하여 부분 배열의 합 중 최대의 값을 추려내고 있다.

        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);

이 방법의 아레의 시간 복잡도는 갖는다.
$O(n)$

2. Brute Force

주어진 배열에서 각 인덱스를 기점으로 가능한 경우의 수를 모두 걔산하여 최대 합을 구한다.

public int maxSubarrayBruteForce(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j]; // 부분 배열 합 계산
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

코드를 보면 이중 반복문으로 구성이 되어 있기 때문에 카데인 알고리즘 방법 보다 효율적이지 않다.

3. 분할 정복

분할 정복 방법은 주어지는 수열을 절반으로 나누어서 각각의 배열에서 최대 합과 두 배열을 포함하는 부분 배열의 합 이렇게 총 3개의 최대합을 구하여 비교를 하는 방법이다.

public int maxSubarrayDivideConquer(int[] nums, int left, int right) {
    if (left == right) return nums[left]; // 기저 사례

    int mid = left + (right - left) / 2;
    int leftMax = maxSubarrayDivideConquer(nums, left, mid);
    int rightMax = maxSubarrayDivideConquer(nums, mid + 1, right);
    int crossMax = maxCrossingSum(nums, left, mid, right);

    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

private int maxCrossingSum(int[] nums, int left, int mid, int right) {
    int leftSum = Integer.MIN_VALUE, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    return leftSum + rightSum;
}

$O(n\log n)$ 시간 복잡도를 갖고 있어 Brute Force 방법 보다는 효율적인 방법이지만 카데인 알고리즘에 비해서는 좋지 않다.

동작 과정

2	3	-6	1	3	-1	2	4

해당 수열이 있을 때 부분 수열의 합 중 가장 큰 값을 구하는 과정을 살펴 보자

예제에 사용할 코드는 아래와 같다.

public int maxSubarrayKadane(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

일단 초기의 maxSum, currentSum의 값은 2로 초기화가 되어있다.

i == 1
i가 1일 경우 최대 합은 이전 단계의 최대 합인 2를 이용하여 현재 단계의 최대 합을 구한다.
currentSum == 5, maxSum ==5
i == 2
전 단계의 최대 합을 이용하여 현재 최대의 합을 구한다.
currentSum의 값은 -1이 된다. 이는 5 보다 작기 때문에 maxSum은 기존 값을 유지한다.
i == 3
nums[3]은 nums[3] + currentSum 보다 크기 때문에 현재 단계의 최대 합은 nums[3]이다.

현재 단계의 최대 합은 nums[3]이기 때문에 부분배열의 최대 합을 구하기 위해서는 i의 값이 3 이전의 인덱스는 최대 합과는 상관없게 된다.
i == 4
현재 최대의 합은 전 단계의 최대의 합과 nums[i]를 더하여 4가 된다.