최대 부분합 문제 Maximum Subarray 파헤치기

안녕하세요

블레이즈 테크노트 

블레이즈 입니다. 

 

여태까지 삽입 정렬과 합병 정렬에 대해서 살펴봤습니다. 

 

특히 합병 정렬을 다루면서 Divide-Conquer (분할정복)에 대해서 다루었는데요, 

 

 

이번에는 또 다른 Divide and Conquer (분할정복) 알고리즘인 최대 부분합 문제를 파헤쳐보도록 하겠습니다. 

 

최대 부분합 문제는 주식 판매 수익을 최대화하는 문제로 설명할 수 있습니다. 

 

주어진 기간동안 주식 가격이 있다면 

언제 사서 언제 팔아야 할까요?? 

당연히 가장 싼 날 주식을 사서 가장 비싼 날 팔아야 겠죠? 

이를 최대 부분합 문제, Maximum Subarray Problem이라고 합니다. 

위 그림을 보면 2일에 사서 5일에 팔면 될 것 같습니다. 

 

 

그렇다면 이 문제를 어떻게 알고리즘화할 수 있을지 살펴보도록 하겠습니다. 

 

 

 

Brute-Force 란, 가장 직관적이면서 쉬운 풀이입니다. 

문제 해결은 가능하지만 효율적이지 않은 경우가 많습니다. 

 

주식을 살 수 있는 모든 날에 대해서 모든 팔 수 있는 날을 다 계산해보고

그 차익이 가장 큰 날을 고르는 것이 

Brute-Force 알고리즘입니다. 

 

이 경우, 알고리즘의 시간복잡도는 n 제곱이 되겠네요! 

 

하지만 n 제곱 복잡도는 너무 비용이 큽니다. 

그래서 시간복잡도를 줄여보는 방법을 생각해보겠습니다. 

 

 

두 번째 방법은 가격의 변화를 따라가는 표를 하나 더 만드는 것입니다. 

 

그러면 이 가격 변화표만 보더라도 가장 차익을 실현하기 좋은 시점을 알기가 편해집니다. 

 

1번 방법보다는 계산량이 줄어들었습니다. 

하지만 n에 대한 시간복잡도를 계산해보면 여전히 n 제곱입니다. 

 

 

그래서 이 문제를 Divide & Conquer (분할정복) 로 해결하는 알고리즘을 소개하고자 합니다. 

 

 

이 알고리즘의 핵심 개념은 mid 라는 가운데 지점을 세우는 것입니다. 

 

이 mid를 기준으로 최대부분합이 존재하는 구역은 

왼쪽 

혹은 오른쪽 

혹은 mid를 건너서 왼쪽부터 오른쪽 

 

세 경우 중 하나입니다. 

 

이렇게 문제를 3 종류로 나눴습니다. 

 

이렇게 나눈 이유는 왼쪽에서 답을 구하는 문제와 오른쪽에서 답을 구하는 문제는

문제의 크기만 줄어들고 상황은 완전히 동일하기 때문입니다. 

 

이렇게 문제 상황은 동일하되 문제의 크기만 줄이는 방식이 

Divide-Conquer (분할정복)의 핵심입니다. 

 

 

문제 해결방법을 정리하면 다음과 같습니다. 

 

 

이를 해결하기 위해

먼저 mid를 건너는 경우에 대해서 먼저 생각해보겠습니다. 

 

 

mid를 가로지른다는 것은 가장 저렴하게 매수할 수 있는 타이밍이 mid보다 과거이고 

가장 비싸게 매도할 수 있는 타이밍이 mid보다 미래라는 뜻입니다. 

 

 

따라서 우리는 먼저 mid를 기준으로 가장 저렴하게 살 수 있는 시점을 계산할 겁니다. 

 

 

이때, 우리는 절대, mid 이전에 매도하지 않을 것입니다. 

 

다시 말해 우리는 무조건 mid 이후에 팔 것이기 때문에 

mid를 기준으로 시점 x부터 mid까지의 수익이 최대인 시점을 구해야 합니다. 

 

이를 정리해보면 아래와 같은 아이디어 구상을 할 수 있습니다. 

 

right에 대해서도 마찬가지의 아이디어 구상을 할 수 있습니다. 

 

이번엔 최적의 매도 타이밍을 잡기 위한 것만 달라집니다. 

 

최종적으로 이 알고리즘을 코드로 구현하면 다음과 같습니다. 

 

 

검은 색 글씨는 코드이고 파란색 글씨는 이 코드의 시간복잡도 time complexity 계산을 위한 설명입니다. 

 

이렇게 Find_Max_Crossing_Subarray()를 구현했다면 

나머지는 잘 Combine 하는 일 밖에 없습니다. 

 

 

아래의 코드가 Find-Maximum-Subarray() 입니다.

이를 보시면 맨 마지막에 left_sum과 right_sum, cross_sum 중 최댓값을 골라 리턴합니다. 

 

 

 

이 Find-Maximum-Subarray() 역시 

Divide and Conquer (분할정복)으로 구현되었기 때문에 시간복잡도가 재귀적으로 표현됩니다. 

 

 

이러한 Recurrence Relation에 대한 엄밀한 풀이는 다음에 제시할 것입니다만,,, 

일단은 아래의 그림처럼 recursion tree를 이용하면 대체적으로 예측할 수는 있습니다. 

 

 

감사합니다. 

블레이즈테크노트