Kadane's algorithm 이란? (설명)

코딩 문제를 풀다보면 이런 문제가 나옵니다.

 

"배열 A의 요소들 중 연속된 합이 가장 큰 수를 구하시오"

"배열 A의 요소들 중 연속된 합이 가장 큰 배열 요소의 범위를 구하시오"

 

배열 요소중 양수만 있을 경우 모두 다 더해주면 되지만

음수가 들어가면 머리가 복잡해 집니다.

 

직관적으로 풀어버리면 이중 for문을 사용해 각 범위마다 값을 구한 후 구한 값들 중 가장 큰 값을 구해야 합니다.

 

하지만 이는 O(n^2)이 되버리며 코딩 문제에서도 이러한 답은 원하지 않습니다.

 

그리고 이러한 문제는 흔히 볼 수 있으며, 코딩 테스트를 준비하고 있는 분들이라면 기본적으로 손쉽게 풀 수 있어야 한다고 생각합니다.

 

위 문제들은 O(n)으로 풀 수 있는데 Kadane's algorithm을 사용하면 됩니다.

 

위 식이 Kadane's algorithm의 기본 식이며 코드로 표현하면 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    int A[9] = { 1, 2, -10, 4, 12, 15, -1, 2, 3 };
    vector<int> m;
    int max_num = 0;
    
    m.push_back(A[0]);

    for (int i = 1; i < 9; i++) {
        m.push_back((m[i - 1] + A[i] > A[i]) ? m[i - 1] + A[i] : A[i]);
        max_num = max(max_num, m.back());
    }

    cout << max_num << endl;
    return 0;
}​

 

이 원리에 대해 설명하자면, 우선 직관적으로 배열의 합중 최대 값을 구하는 방법은 2가지가 있습니다.

 

max = A[0] +~ A[8].

max = A[1] +~ A[8].

max = A[2] +~ A[8].

max = A[3] +~ A[8].

.

.

.

max = A[8].

 

다른 하나는

 

max = A[0].

max = A[0] +~ A[1].

max = A[0] +~ A[2].

max = A[0] +~ A[3]

max = A[0] +~ A[4].

.

.

.

max = A[0] +~ A[8].

 

이렇게 되면 모든 경우의 수를 다 더한 것이 됩니다.

 

이중 Kadane's algorithm은 2번째 방법을 이용합니다.

 

여기서 관건은 바로 "연속된 최대 합" 입니다.

 

 

 

 

 

 

 

 

 

 

 

문제에서 요구하는 것은 연속된 배열 요소중 최대 값을 구하는 문제이기 때문에 

sum 부분은 연속된 최대값의 경우만 넣었습니다.

 

 

그럼 연속딘 합 중 최대 값인 경우를 다른 색으로 표시해 보겠습니다.

 

 

 

색칠을 하면 이런식으로 되는데 그림을 보면 딱 감이 잡힐 것입니다.

 

최대 값을 구한 후 다음 값과 더해 다음 값이 더 크면 계속 더해주고 다음 값이 작으면 기존의 최대 값을 유지시켜 줍니다.

 

저희가 주목해야할 부분은 4회전과 7~8회전 부분인데, 

 

우선 4회전 부분을 보게되면 이전 최대 값은 3이고, -10을 통해 계산하 경우 -10 + 3 = -7인 경우와 -10 + 3 + 4 = -3, -10 + 4 = -6인 부분이 존재 합니다.

 

하지만 이 모든 값들은 연속해서 더했을 때 모두 음수가 나오며 A[3] 값인 4보다 작습니다. 즉, 연속된 합을 구해도 혼자인 A[3]보다 값이 작다는 소리입니다.

 

이경우 최대 값을 4로 갱신해주고 최대값인 4인 지점부터 다시 더해나가게 됩니다.

 

즉, A[0] ~ A[2]까지의 값들은 이제 상관 없는 값들로 되어버린 것입니다. (한마디로 신경을 안써도 됨)

 

 

7~8회전 분을 보면 -1을 만나 잠시 최대 값의 변화가 일어납니다. 떄문에 6회전과 7회전의 최대 값은 동일한 것을 알 수 있습니다.

 

하지만 8회전에서 2를 더해 31보다 큰 32가 되었습니다. 이 경우도 7회전에서의 값인 30 + 2가 되었기 때문에 저렇게 된 것입니다.

 

그렇다면 7회전 값은 갖고 있으면서 회전마다 나온 최대 값들만 따로 저장해 보관한다면 문제가 없이 계산할 수 있습니다.

 

※7~8회전 부분은 저도 쉽게 설명하기가 어렵습니다. 그러니 되도록 코드와 같이 보시기 바랍니다. 그러면 훨씨 수월할 걸로 생각됩니다.

 

 

 

 

이러한 일련의 과정을 정리한 알고리즘이 Kadane's algorithm 이며 식은 아래와 같이 정의 됩니다.

 

 

 

 

긴 글 봐주셔서 감사합니다.!!