C++로 주어진 합을 갖는 부분 배열 찾기 (음수가 아닌 정수)

이 문제에서는 정렬되지 않은 상태로 저장된 N개의 양의 정수로 이루어진 배열 arr[]가 주어지며, 우리의 목표는 주어진 합(sum)과 같은 값을 갖는 부분 배열(subarray)을 찾는 것입니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력 : arr[] = {2, 5, 1, 4, 6, 9, 5}, sum = 11
출력 : subarray = {1, 4, 6}

설명 −

부분 배열의 합 = 1 + 4 + 6 = 11

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

가장 직관적인 해결 방법은 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문으로 시작 인덱스를 정하고, 안쪽 반복문으로 그 지점부터 시작하는 부분 배열을 하나씩 늘려가며 원소들의 합을 계산합니다. 계산된 합이 주어진 값과 일치하면 해당 부분 배열을 출력하고, 배열 전체를 탐색할 때까지 조건을 만족하는 부분 배열을 찾지 못하면 "찾지 못했다"는 메시지를 출력합니다.

이 방법의 시간 복잡도는 O(n²)입니다.

알고리즘

1단계 − 배열을 순회하며 시작 인덱스 i(0 ~ n-1)를 선택합니다.
- 1.1단계 − i부터 시작하는 모든 부분 배열에 대해 원소들의 합을 차례로 구합니다.
- 1.2단계 − 현재 부분 배열의 합이 주어진 sum과 같으면 해당 부분 배열을 출력합니다.
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 (currSum > sum || 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 = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

출력

Subarray with given sum : { 1 4 6 }

방법 2: 가변 크기 슬라이딩 윈도우

더 효율적인 접근 방식은 슬라이딩 윈도우(sliding window)와 유사하지만 윈도우 크기가 고정되지 않은 방법입니다. 배열의 첫 번째 원소부터 시작하여 윈도우에 원소를 하나씩 추가하다가, 윈도우의 합이 주어진 sum보다 커지면 다시 sum 이하가 될 때까지 앞쪽 원소를 제거합니다. 이 과정을 배열 전체를 순회할 때까지 반복합니다.

탐색 중 어느 시점이라도 윈도우의 합이 주어진 sum과 같아지면 해당 부분 배열을 출력하고, 끝까지 찾지 못하면 "No subarray found!"를 출력합니다.

각 원소가 최대 한 번 추가되고 한 번 제거되므로 이 방법의 시간 복잡도는 O(n)으로, 브루트 포스 방식보다 훨씬 효율적입니다. 단, 이 기법은 배열의 모든 원소가 음수가 아닐 때에만 올바르게 동작한다는 점에 유의해야 합니다.

알고리즘

초기화 − windowSum = arr[0], startIndex = 0, endIndex = 1

1단계 − endIndex로 배열을 순회합니다.
- 1.1단계 − windowSum이 sum보다 작거나 같은 동안에는 윈도우 끝에 원소를 계속 추가합니다(windowSum += arr[endIndex]).
- 1.2단계 − windowSum이 sum보다 커지면 windowSum ≤ sum이 될 때까지 윈도우 앞쪽의 원소를 제거합니다(windowSum -= arr[startIndex], startIndex++).
- 1.3단계 − windowSum == sum이면 해당 부분 배열을 출력합니다.
2단계 − 배열 전체를 탐색한 후에도 찾지 못했다면 '불가능(not possible)'을 출력합니다.

예제 코드

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#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 windowSum = arr[0], startIndex = 0, endIndex;
   for (endIndex = 1; endIndex <= n; endIndex++) {
      while (windowSum > sum && startIndex < endIndex - 1) {
         windowSum -= arr[startIndex];
         startIndex++;
      }
      if (windowSum == sum) {
         cout << "Subarray with given sum : ";
         printSubArray(arr, startIndex, endIndex);
         return 1;
      }
      if (endIndex < n)
         windowSum += arr[endIndex];
   }
   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 = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

출력

Subarray with given sum : { 1 4 6 }