Maximum Subarray Problem 은 주어진 1 차원 배열 A [1 … n]의 숫자 내에서 가장 큰 합을 갖는 연속 서브 배열을 찾는 문제입니다.

Maximum Subarray ( In Orange )

위 예시에서의 연속된 배열의 합의 최대 값은 2, 4, 1, -1, 5 의 합인 11 입니다.
어떻게 가장 큰 연속된 배열을 구하는지 알고리즘 통해 알아보겠습니다.

1. 모든 경우의 수를 합산 ( Brute Force )

가장 쉽지만 가장 비효율적인 방식인 모든 경우의 수를 구하여 계산하는 방법입니다.

배열 A의 요소들의 모든 하위 배열을 구하고 그 합들을 비교해서 가장 큰 값을 구하게됩니다.

def max_sub_array_sum1(numbers):
    max_so_far = 0
    max_start = 0
    max_end = 0

    for i in range(len(numbers)):
        for j in range(len(numbers[i:])):
            max_sum = sum(numbers[i:i+j+1])
            if max_so_far < max_sum:
                max_so_far = max_sum
                max_start = i
                max_end = i + j

    return numbers[max_start:max_end+1], max_so_far

if __name__ == '__main__':
    a = [2, -3, 2, 4, 1, -1, 5, -3, 2]
    max_arr, sum_val = max_sub_array_sum1(a)
    print('arr = {0}, sum = {1}'.format(max_arr, sum_val))
arr = [2, 4, 1, -1, 5], sum = 11

위 방법은 쉽게 떠올릴 수 있는 방법이지만 매우 비효율적이고 느립니다.

그래서 우리는 좀 더 향상된 방법으로 결과를 구해보도록 하겠습니다.

2. Kadane’s Algorithm (카데인 알고리즘)

Dynamic Programming ( 다이나믹 프로그래밍 )

카데인 알고리즘을 알아보기전에 밀접한 관련이 있는 다이나믹 프로그래밍에 대해 알아보겠습니다.

다이나믹 프로그래밍이란 복잡한 문제를 간단한 여러개의 하위 문제(subproblem)로 분리하여 해결한 결과를 다시 결합하여 최종적인 해결책을 찾는 방법인데요.

여러개의 하위 문제들을 해결할때마다 답을 저장하고 이후에 동일한 하위 문제가 나타나면 저장되어있던 답을 사용하여 간단히 해결할 수 있습니다.

이렇게 설명하면 감이 안잡히시죠?

그래서 다이나믹 프로그래밍에 대해 쉽게 나타낸 예시가 있습니다.
4살짜리에게 다이나믹 프로그래밍을 설명하는 방법인데요.

종이에 1+1+1+1+1+1+1+1 을 적어놓고 아이에게 물어본다.
” 이것을 다 더하면 무엇과 같지?”

이 질문에 대해 아이는 ‘8’ 이라고 대답하였다.

그리고 왼쪽에 1+ 를 추가한 후 아이에게 다시 한번 물어보면
아이는 빠르게 ‘9’라고 답한다.

그리고 아이에게 어떻게 9인지 빠르게 알 수 있었니? 라고 물어보면 아이는 이렇게 답한다.
“그냥 1을 더했어요”

그렇다 기존에 계산해놓았던 답을 기억하고 있었으므로 1을 9번 다시 더할 필요 없이
기억해두었던 답 8에 추가된 1을 더했을 뿐이다.

이처럼 다이나믹 프로그래밍도 ‘시간을 절약하기 위해 어떤 것을 기억하는것’ 이다.

https://www.quora.com/How-should-I-explain-dynamic-programming-to-a-4-year-old/answer/Jonathan-Paulson

결국 다이나믹 프로그래밍은 동일한 문제를 다시 계산하지 않도록 저장해두었다가 다시 사용하는방법을 나타내는 것입니다.

그리고 다이나믹 프로그래밍을 이용한 알고리즘이 바로 Kadane’s Algorithm (카데인 알고리즘) 입니다.

Kadane’s Algorithm (카데인 알고리즘) 이해하기

처음에 소개해드렸던 Maximum Subarray Problem 을 해결하는 방법을 통해서 카데인 알고리즘을 알아보겠습니다.

우선 1차원 배열의 요소 중 A[3] 과 A[4] 의 부분합을 구하는 경우를 이미지로 나타내보겠습니다.

A[4]의 부분합을 계산할때 빨간색 화살표가 가리키는 대상들만 부분합을 구해주면 된다.

위 이미지의 A[3]와 A[4] 의 부분합 계산을 비교해보면 ( A[3]의 부분합 + A[4] ) = ( A[4]의 부분합 ) 이라는 것을 알 수 있는데요.

이러한 규칙이 모든 요소의 부분합을 계산하는 경우 동일하게 적용되어 아래처럼 나타낼 수 있습니다.

A[n]의 부분합 = A[n-1] 부분합 + A[n]
=> A[n] 의 local maximum = A[n-1] local maximum + A[n]

따라서, 매번 모든 요소들의 부분합을 다시 계산해줄 필요없이,
바로 이전 요소의 부분합을 알고 있다면 현재 요소의 부분합을 재계산하지 않아도 구할 수 있습니다.

그리고 현재 요소의 local maximum 도 이전 요소의 local maximum을 이용하여 구할 수 있습니다.

이제 이 규칙들을 바탕으로 카데인 알고리즘을 구현해보도록 하겠습니다.

def max_sub_array_sum2(numbers):
    max_so_far = 0
    max_ending = 0
    max_start = 0
    max_end = 0
    s = 0

    for i in range(len(numbers)):
        max_ending += numbers[i]

        if max_so_far < max_ending:
            max_so_far = max_ending
            max_start = s
            max_end = i

        if max_ending < 0:
            max_ending = 0
            s = i + 1

    return numbers[max_start:max_end+1], max_so_far

if __name__ == '__main__':
    a = [2, -3, 2, 4, 4, -1, 5, -3]
    max_arr, sum_val = max_sub_array_sum2(a)
    print('arr = {0}, sum = {1}'.format(max_arr, sum_val))
arr = [2, 4, 1, -1, 5], sum = 11

코드에서 max_so_far 변수에는 local maximum 을 저장하며, max_ending 변수는 현재 요소의 부분합을 저장합니다.

그리고 요소마다 루프를 돌면서 기존 local maximum 보다 현재의 부분합이 더 크다면 local maximum 을 현재 부분합으로 변경해주고
max_ending 변수가 0 보다 작다면 0으로 변경해줍니다.

그리고 해당 코드에는 최대 부분합의 요소들을 구하기위해 max_start, max_end 요소를 별도로 저장하는데,
단순히 최대 부분합만 구해야 한다면 해당 코드는 제거해도 무방합니다.

그리고 결과는 동일하지만 실행속도를 측정해보면 코드의 효율성이 큰 차이가 나는 것을 알 수 있습니다.

WorkingTime[max_sub_array_sum1]: 0.00004697 sec
WorkingTime[max_sub_array_sum2]: 0.00000691 sec

이상으로 카데인 알고리즘에 대해 알아보았는데요.

알고리즘을 쉽게 설명하려고 노력하였는데.. 생각처럼 쉽지 않네요 ㅠㅠ

이해가 안가시는 부분이나 틀린점은 언제든 댓글로 지적해주세요!

감사합니다. 😄