본문 바로가기

Algorithm/이론

Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘)

오늘도 어김없이 Codility의 문제를 풀다가, brutal force로 풀기는 정말 싫은데 도저히 다른 방법이 떠오르지 않아서 검색하다가 발견한 알고리즘에 대해 글을 써보려 한다.

검색을 해보니 Kadane's Algorithm에 대한 설명을 정말 잘 해준 포스트가 있었다.

포스트로 가기 👉 Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?
유튜브 비디오 보기 👉 https://www.youtube.com/watch?v=86CQq3pKSUw

위의 포스트와 비디오를 기반으로, Kadane's Algorithm이란 무엇인가를 설명하고자 한다.
우선, 다이나믹 프로그래밍에 대해서 집고 넘어갈 필요가 있다.

 

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


다이나믹 프로그래밍이란 기본적으로 복잡하게 반복해야 하는 문제를 여러개의 문제로 나눈 후, 그 문제들을 매 번 반복하지 않고, 그 값을 저장해 두었다가 재 사용하는 기법이다.

위에 달아놓은 블로그에 가서도 볼 수 있지만, 네 살짜리 아이에게 다이나믹 프로그램을 어떻게 설명해야하나요? 라는 질문에 달린 명쾌한 답변이 있었다.

종이에 "1+1+1+1+1+1+1+1 =" 을 쓰고, 아이에게 답이 무엇이냐고 묻는다.
아이 : (숫자를 하나씩 센 후) 8!
문제의 왼쪽에 "1+"을 덧붙인 후, 아이에게 다시 답을 묻는다.
아이: (빠르게) 9!
어떻게 9인지 빨리 알았니?라고 물으면 아이는 "그냥 1을 더했어요!" 라고 말한다.
왜냐하면 8을 기억해놨다가 1을 더했을 뿐, 1부터 9까지 다시 셀 필요가 없는 것이다! 다이나믹 프로그래밍은 그저 "시간을 절약하기 위해 어떤 것을 기억하는 것"이다.

다이나믹 프로그래밍에는 여러가지가 있지만, Kadane’s Algorithm을 활용한 대표적인 문제인 Maximum Subarray(최대 부분 합 구하기) 문제를 통해 Kadane’s Algorithm이 어떻게 동작하는지 알아보고자 한다.

 

 

Maximum Subarray Problem(최대 부분 합 구하기)


최대 부분합 문제는 주어진 1차원 배열의 부분 배열의 합 중 최대인 것을 구하는 문제이다. 

A = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

만약 배열이 위와 같이 주어진다면 가장 큰 합을 가진 부분 배열은 [4, -1, 2, 1]로, 최대 합 6을 가진다.

 

Brute Force 접근법

위의 문제를 Brute Force로 푼다면 가능한 부분 배열들을 모두 살펴본 후 합을 구해서 가장 큰 값을 찾는 방식으로 풀 수 있다. 위의 배열을 예로 들면, 배열 A의 index 0번에서 시작해서, A[0]번과 가능한 모든 부분 배열의 합을 구한다. 그리고나서 똑같은 방식을 A[1], A[2] ... A[n-1]번까지 반복한다. 이를 아래의 과정으로 풀어보았다.

 

1. 배열 A의 인덱스 0번에서 시작해서, A[0]번과 가능한 모든 부분 합을 구한다.

2. A[0]의 가능한 모든 부분합 중에서 가장 큰 부분합을 localMaximum_0 이라고 한다.

3. 1, 2의 방식을 A[1], A[2] ... A[n-1]번까지 똑같이 반복한다.

4. 인덱스 0부터 N-1까지 각 인덱스에 해당하는 localMaximum_0~localMaximum_N-1 이 구해졌을 것이다

5. 구해진 localMaximum 들 중에서 가장 큰 값을 찾는다. 이 값이 globalMaximum, 최종적으로 가장 큰 부분합이다.

 

하지만 이처럼 푸는 방식은 배열의 사이즈가 커질 수록, 위 과정의 1-2번을 반복해야하는 횟수도 더 커진다. 따라서 문제를 푸는데 시간 복잡도가 O(n^2)가 되므로 좋은 방법이라고 할 수 없다.

 

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

이번에는 카데인 알고리즘으로 푸는 방법을 알아보자.

카데인 알고리즘을 증명하기 위해 우선, 위의 brutal foce방법을 A[0]이 아닌 A[n-1]에서(뒤에서 부터) 시작하도록 한다. 이 때, 위의 예제를 이용해 A[4] (= -1) 과 A[5] (=2)가 최대 부분합을 구하는 것을 보면 아래와 같다.

 

이 과정을 자세히 본다면 아래와 같은 규칙을 발견할 수 있다.

 

A[5]의 부분합을 계산할 때 A[4]까지의 부분합을 구하는 부분(회색 음영 박스)을 생략할 수 있다.

 

A[4]의 부분합 + A[5]를 통해서 A[5]의 부분합을 구할 수 있기 때문에 A[4]의 부분합을 알고 있다면 A[5]의 모든 부분합을 처음부터 다시 재계산하지 않아도 우리는 A[5]의 부분합을 알 수가 있다.

 

따라서 우리는 localMaximum을 구할 때, 위의 이미지에서 빨간색 화살표로 표시한 부분만 고려해서 둘 중 더 큰 값을 가지는 값을 localMaximum으로 보면 된다. 

 

첫번째 빨간색 화살표는 A[5] 이고, 두번째 빨간색 화살표는 A[4]의 부분합을 포함하고있는 A[5]의 부분합 중 가장 큰 값인 A[4]의 localMaximum + A[5]이다. 이 두 값만 비교해서 더 큰 값을 A[5]의 localMaximum 값으로 보면 된다. 식으로 표현하면 아래와 같다.

localMaximum[i] = max(A[i], A[i] + lacalMaximum[i-1])

참고로, A[0]의 localMaximum은 A[0]의 값 그 자체이다.

 

따라서 Brutal Force 접근법과 달리 배열을 한번만 순회하면 되기 때문에 Kadane's Alogorithm의 시간 복잡도는 O(n)이다.

 

코드로 풀어보기 - Javascript

function maxSumSubArray(A) {
    let localMax = A[0];
    let globalMax = A[0];
    
    for(let i = 1; i < A.length; i++) {
    	localMax = Math.max(A[i], localMax + A[i]);
        if(localMax > globalMax) {
        	globalMax = localMax;
        }
    }
    
    return globalMax;
}

위의 코드를 예로 들어 배열 A를 넣고 돌려보면 return 값으로 6이 반환된다.