Dynamic Programming - 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)이다.