최대 연속 부분 구간 합 문제 (여러가지 풀이)

최대 연속 부분 구간 합 문제로 어떤 하나의 문제를 다양한 방법으로도 풀 수 있는 경우가 있다는 것을 확인하고 시간복잡도가 어떻게 차이가 나는지 확인해보자.

 

참고: 이 내용은 `프로그래밍 대회에서 배우는 알고리즘 문제해결전략 - 구종만 지음`에서 나온 내용을 일부 가져왔다.

 

---

문제

 

정수로 이루어진 1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간의 합을 구하는 문제이다.

예를 들어 다음과 같인 배열이 있을 때, 연속된 부분 구간 중 최대 합은 12 이다.

 

[ -5, 10, -5, 7, 0, -3, 1, -5, -2, 5 ]

=> [ 10 , -5, 7 ]

=> 10  + (-5) + 7 = 12

 

---

풀이 1 : 모든 길이에 대해 모든 합 계산하기

 

첫번째 인덱스 부터 시작해서 길이가 1, 2, 3, ...인 연속된 구간의 합을 모두 구하는 (무식한?) 방법을 사용해보자.

const int MIN = numeric_limits<int>::min();

int getMaxSum(const vector<int>& v) {
    const int s = v.size();
    int ret = MIN;
    
	// i번째 수부터 마지막까지 확인
    for (int i=0; i<s; ++i) {
    	// 길이(j)를 하나씩 늘리기
        for (int j=i; j<s; ++j) {
            int sum = 0;
            // [i..j]의 합 구하기
            for (int k=i; k<j+1; ++k) {
                sum += v[k];
            }
            ret = max(sum, ret);
        }
    }

    return ret;
}

3중 반복문으로 시간 복잡도는 O(N^3) 이다.

 

---

풀이 2: 모든 합 계산하기

 

사실 이번 풀이는 풀이 1을 좀 더 간소화 한 것에 불과하다. 길이에 대한 반복문을 하나로 줄였다.

int getMaxSum2(const vector<int>& v) {
    const int s = v.size();
    int ret = MIN;

    for (int i=0; i<s; ++i) {
        int sum = 0;
        // [i..j]에 대한 합 구하기
        for (int j=i; j<s; ++j) {
            sum += v[j];
            ret = max(sum, ret);
        }
    }

    return ret;
}

풀이 1번 보다 훨씬 빨라질 것이라고 확신할 수 있는 풀이 2이다. 시간 복잡도는 O(N^2)이다.

---

풀이 3: 분할 정복 (Divide and Conquer)

 

뭔가 이 문제에서 분할 정복을 떠오르기는 쉬워보이지 않지만 어차피 구간의 최대 합을 구하는 거면 그 구간을 잘게 쪼갠 다음 잘개 쪼갠 구간들 중 최대합을 각각 구하고 구간들을 다시 합쳐서 값을 비교하면 될 것이다.

 

즉, 좌-우로 쪼겐다고 했을 때,

 

0. 기저(base case)는 확인하려는 구간의 길이가 1일 때이다. (길이가 1일때까지 쪼갠다.)

1. left ~ mid와 mid+1 ~ right로 나눌 수 있을 것이다. (right는 배열의 길이가 아닌 마지막 index 번호이다.)

2.  left ~ mid에서의 연속된 숫자의 최대합을 구하고 mid+1 ~ right에서도 마찬가지로 최대합을 구한다.

(여기서 주의 할 점은 나중에 좌-우를 합쳐서 최대합을 구하려고 할 때, 연속된 부분이어야 하므로, 왼쪽은 mid부터 시작하여 left까지 값을 더해야 하고, 오른쪽은 mid+1부터 right까지 값을 더하면서 최대합을 구해야 한다는 점이다.)

3. 1~2내용을 반복

4. 왼쪽부분에서의 연속된 구간 최대합(l)과 오른쪽 부분에서의 연속된 구간 최대합(r) 그리고 이 둘을 연속으로 이었을 때 나올 수 있는 최대값(l + r)을 서로 비교한다.

5. 위에서 비교한 값 중 가장 큰 것을 반환한다.

 

int getMaxSum3(const vector<int>& v, const int left, const int right) {
	// 기저 사례 (길이가 1일때 그 자체가 최대합이다.)
    if (left == right) return v[left];

    int mid = (left + right) >> 1; // (left +right) / 2 와 같다.
    int l = MIN; // 왼쪽 부분에서의 연속된 구간의 최대 합
    int r = MIN; // 오른쪽 부분에서의 연속된 구간의 최대 합
    int sum = 0; // 합을 계산할 임시 변수

    // l + r 시에 연속된 배열이어야 하기 때문에 mid 부터 하나씩 내려감!
    for (int i=mid; i>=left; --i) {
        sum += v[i];
        l = max(sum, l);
    }

    sum = 0;

    for (int i=mid+1; i<=right; ++i) {
        sum += v[i];
        r = max(sum, r);
    }
	
    // 좌우 비교
    int single = max(getMaxSum3(v, left, mid), getMaxSum3(v, mid+1, right));
    // 합쳤을 때와 비교
    return max(single, l + r);
}

시간복잡도는 O(NlogN)이 된다!!!

 

---

풀이 4: 점화식을 이용한 Down-Top 메모이제이션 (동적 계획법)

 

배열을 순차적으로 확인하여 구간 합의 최대 값을 찾으려고 할 때 조금만 더 생각해보자.

[a, b, c, d, e, ...] 라는 배열이 있다.

A를 a를 마지막으로 하는 구간의 최대합, B를 b를 마지막으로 하는 구간의 최대합... 이라고 했을 때, 

끝을 포함하는 연속된 부분의 합과 끝 값 중 큰 값이 해당 값이 된다.

A = a

B = A+b > b ? A+b : b

C = B+c > c ? B+c : c

...

 

즉, I(i번째 원소를 끝으로 갖는 구간의 최대합)은 `(I-1) + v[i]`와 `v[i]`중 큰 값이 된다.

 

이를 점화식으로 나타낸다면,

Ai = max(Ai-1 + v[i], v[i]) => 

 

위 식을 코드로 표현하면 다음과 같다.

int getMaxSum4(const vector<int>& v) {
    const int s = v.size();
    int ret = MIN;

    int psum = 0;
    for(int i=0; i<s; ++i) {
        psum = max(psum, 0) + v[i]; // psum = max(psum + v[i], v[i]);
        ret = max(ret, psum); // 가장 큰 값 찾기
    }

    return ret;
}

무려 반복문 하나로 이 문제를 풀 수 있다!! (시간복잡도: O(N))

 

---

이게 얼마나 차이나는지는 시간복잡도에 대한 그래프가 말해줄 것이다.

 

아니면, 간단하게 생각해보자.

v의 길이가 1000이라고 했을 때,

풀이1은 1000^3 = 1000000000,

풀이2는 1000^2 = 10000000,

풀이3은 1000 * lg1000 ~~ 30000,

풀이4는 1000...

 

물론 v의 길이가 훨신 더 커지면 거의 N^3와 N 값은 정말 매우 큰 차이가 날 것이고, 이에 따라 시간도 오래 걸릴 것이다.

 

이처럼 어떤 문제를 푸는 데에 여러가지 방법이 존재할 수는 있지만, 그 여러가지 방법 중 가장 효율적인 방법을 찾아 고민하고 그렇게 문제를 해결하는 것이 우리들이 계속해서 해야하는 일이라고 생각한다.