C++에서 주어진 합을 갖는 부분 배열 찾기 – 음수 처리 완벽 가이드

문제 개요

이번 문제에서는 정렬되지 않은 상태로 저장된 N개의 정수로 구성된 배열 arr[]가 주어지며, 그중 합이 주어진 값(sum)과 일치하는 부분 배열(subarray)을 찾아야 합니다. 배열에 음수가 포함될 수 있다는 점이 핵심인데, 양수 전용 문제에서 흔히 쓰이는 '합이 초과하면 탐색을 중단하는' 최적화 기법은 오히려 정답을 놓치게 만들 수 있습니다.

예제로 문제 이해하기

입력 : arr[] = {2, 5, -1, 4, 6, -9, 5}, sum = 14
출력 : 부분 배열 = {5, -1, 4, 6}

설명 −

부분 배열의 합 = 5 + (-1) + 4 + 6 = 14

방법 1: 중첩 반복문(브루트 포스)

가장 직관적인 해결책은 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문으로 시작 인덱스를 하나씩 이동하고, 안쪽 반복문으로 해당 시작점에서 만들 수 있는 모든 부분 배열의 합을 계산합니다. 합이 목표값과 같아지는 순간 해당 부분 배열을 출력하고 종료하며, 모든 경우를 확인한 후에도 찾지 못했다면 존재하지 않는다는 메시지를 출력합니다.

주의할 점은, 음수가 포함된 배열에서는 누적 합이 일시적으로 목표값을 초과하더라도 이후 다시 감소할 수 있으므로 조기 종료 조건을 두면 안 된다는 것입니다.

알고리즘

• 1단계 − 배열을 처음부터 끝까지 순회합니다(i = 0 ~ n-1).

  • 1.1단계 − 각 시작 위치에서 가능한 모든 부분 배열의 합을 구합니다.

  • 1.2단계 − 현재 부분 배열의 합이 주어진 값과 같으면 해당 부분 배열을 출력합니다.

• 2단계 − 모든 요소를 확인한 후에도 부분 배열을 찾지 못했다면 '조건에 맞는 부분 배열이 없습니다!'라고 출력합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

void printSubArray(int arr[], int i, int j) {
   cout << "{ ";
   for (; i < j; i++)
      cout << arr[i] << " ";
   cout << "}";
}

int findSubArrayWithSum(int arr[], int n, int sum) {
   int currSum;
   for (int i = 0; i < n; i++) {
      currSum = arr[i];
      for (int j = i + 1; j <= n; j++) {
         if (currSum == sum) {
            cout << "Subarray with given sum : ";
            printSubArray(arr, i, j);
            return 1;
         }
         // 음수가 있으므로 합이 초과되어도 중단하지 않음
         if (j == n)
            break;
         currSum += arr[j];
      }
   }
   cout << "No subarray found";
   return 0;
}

int main() {
   int arr[] = { 2, 5, -1, 4, 6, -9, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 14;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

실행 결과

Subarray with given sum : { 5 -1 4 6 }

이 방법의 시간 복잡도는 O(n²)이며 추가 공간은 O(1)입니다. 배열 크기가 작다면 충분하지만, 입력이 커질수록 비효율적입니다.

방법 2: 해시맵을 이용한 효율적 풀이

더 나은 접근 방식은 해시맵(unordered_map)을 활용하는 것입니다. 핵심 아이디어는 누적 합(prefix sum)입니다. 인덱스 0부터 현재 인덱스 i까지의 누적 합을 curr_sum이라 할 때, 어떤 이전 인덱스 p까지의 누적 합이 curr_sum − sum과 같다면, 인덱스 p+1부터 i까지의 부분 배열의 합은 정확히 sum이 됩니다. 따라서 매 인덱스에서 해시맵에 curr_sum − sum이라는 키가 존재하는지만 확인하면 됩니다.

이 방식은 음수가 포함되어 있어도 정확하게 동작합니다. 모든 누적 합을 해시맵에 기록해 두고 필요할 때 조회하는 구조이기 때문에, 누적 합이 증가만 하지 않는 상황에서도 답을 놓치지 않습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

void printSubArray(int arr[], int i, int j) {
   cout << "{ ";
   for (; i <= j; i++)
      cout << arr[i] << " ";
   cout << "}";
}

void findSubArrayWithSum(int arr[], int n, int sum) {
   unordered_map<int, int> map;
   int curr_sum = 0;
   for (int i = 0; i < n; i++) {
      curr_sum += arr[i];
      // 처음부터 현재 인덱스까지의 합이 sum인 경우
      if (curr_sum == sum) {
         cout << "SubArray with the given sum : ";
         printSubArray(arr, 0, i);
         return;
      }
      // curr_sum - sum을 누적 합으로 갖는 이전 지점이 있는지 확인
      if (map.find(curr_sum - sum) != map.end()) {
         cout << "SubArray with the given sum : ";
         printSubArray(arr, map[curr_sum - sum] + 1, i);
         return;
      }
      map[curr_sum] = i;
   }
   cout << "No subarray found!";
}

int main() {
   int arr[] = { 2, 5, -1, 4, 6, -9, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 14;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

실행 결과

SubArray with the given sum : { 5 -1 4 6 }

복잡도 비교

결론적으로, 음수를 포함한 배열에서 주어진 합의 부분 배열을 찾을 때는 해시맵과 누적 합을 이용하는 방법이 가장 효율적입니다. 선형 시간 O(n) 안에 답을 찾을 수 있어 대용량 데이터에서도 안정적인 성능을 보장합니다.