C++로 O(n²) 시간 복잡도의 최대 부분 배열 합 구하기 (브루트 포스 방식)

이 글에서는 C++를 사용하여 O(n²) 시간 복잡도로 최대 부분 배열 합(maximum subarray sum)을 찾는 프로그램을 다룹니다. 이 방법은 모든 경우를 직접 확인하는 순진한(naive) 방식, 즉 브루트 포스 기법에 해당합니다.

알고리즘 개요

핵심 아이디어는 길이가 1부터 n까지인 모든 부분 배열을 검사하면서, 각 단계에서 이전 계산 결과를 재활용해 합을 효율적으로 갱신하는 것입니다.

시작
    배열의 원소들을 입력받는다.
    부분 배열의 길이를 1부터 n까지 반복하는 루프를 만든다.
    그 안에 중첩된 루프를 만들어, 해당 길이의 첫 번째 부분 배열의 합을 계산한다.
    나머지 부분 배열의 합은, 다음 원소를 더하고 해당 부분 배열의 첫 번째 원소를 빼서 구한다.
    현재까지의 전역 최댓값(global max)과 비교하여 더 크면 값을 갱신한다.
    최대 부분 배열과 그 합을 결과로 출력한다.
종료.

예제 코드

#include<iostream>
using namespace std;
int main() {
   int n, i, j, m=-1, s, ini_m, fi_m;
   cout<<"\n배열의 데이터 원소 개수를 입력하세요: ";
   cin>>n;
   int a[n];
   for(i = 0; i < n; i++) {
      cout<<"원소 "<<i+1<<" 입력: ";
      cin>>a[i];
   }
   for(i = 1; i < n+1; i++) {
      s = 0;
      for(j = 0; j < n; j++) {
         if(j < i)
            s += a[j];
         else
            s = s+a[j]-a[j-i];
         if(m< s) {
            ini_m = j-i+1;
            fi_m = j;
            m = s;
         }
      }
   }
   cout<<"\n최대 부분 배열은: ";
   for(i = ini_m; i <= fi_m; i++)
      cout<<a[i]<<" ";
      cout<<"\n최대 부분 배열의 합은: "<<m;
}

실행 결과

배열의 데이터 원소 개수를 입력하세요: 10
원소 1 입력: 1
원소 2 입력: -2
원소 3 입력: 3
원소 4 입력: -4
원소 5 입력: 5
원소 6 입력: -6
원소 7 입력: 7
원소 8 입력: 8
원소 9 입력: -9
원소 10 입력: 10
최대 부분 배열은: 7 8 -9 10
최대 부분 배열의 합은: 16

코드 설명

위 코드의 동작 원리를 살펴보면 다음과 같습니다.

바깥쪽 루프 변수 i는 검사할 부분 배열의 길이를 의미합니다(1부터 n까지).
안쪽 루프 변수 j는 부분 배열의 끝 인덱스를 나타냅니다.
j < i인 초기 구간에서는 처음부터 차례로 원소를 더해 첫 부분 배열의 합을 만듭니다.
그 이후에는 새로 들어오는 원소 a[j]를 더하고, 윈도우에서 벗어나는 원소 a[j-i]를 빼는 방식으로 합을 O(1)에 갱신합니다. 덕분에 완전한 삼중 루프(O(n³))가 아닌 O(n²)의 시간 복잡도를 달성할 수 있습니다.
변수 m은 전역 최댓값을 저장하며, ini_m과 fi_m은 최대 합을 가지는 부분 배열의 시작 인덱스와 끝 인덱스를 기록합니다.

참고 사항

이 예제에서는 편의상 최댓값 m을 -1로 초기화했지만, 배열 전체가 음수인 경우 올바른 결과를 얻으려면 m을 가능한 가장 작은 값(예: INT_MIN)으로 초기화하는 것이 안전합니다. 또한 C++ 표준에서 가변 길이 배열(VLA)은 지원되지 않으므로, 실제 프로젝트에서는 vector<int> 사용을 권장합니다.

더 나아가, 분할 정복(Divide and Conquer) 기법이나 카데인 알고리즘(Kadane's Algorithm)을 활용하면 O(n log n) 또는 O(n) 시간에 문제를 해결할 수 있습니다. 다만 이번 글에서 소개한 O(n²) 방식은 슬라이딩 윈도우 합 갱신의 기본 개념을 익히기에 좋은 출발점입니다.