이 문제에서는 정수 값으로 이루어진 크기 n의 배열 arr[]가 주어지며, 우리의 목표는 합이 0인 부분 배열(subarray)이 존재하는지 확인하는 것입니다.
즉, 주어진 배열 안에서 모든 요소의 합이 0이 되는 연속된 구간이 하나라도 있는지 판별해야 합니다.
문제 이해를 위한 예시
입력: arr[] = {3, 1, -2, 1, 4, 5}
출력: Yes
설명:
부분 배열 {1, -2, 1}의 모든 요소를 더하면 1 + (-2) + 1 = 0이 됩니다. 따라서 조건을 만족하는 부분 배열이 존재하므로 출력은 "Yes"입니다.
해결 접근 방법
1. 브루트 포스(Brute Force) 접근
가장 단순한 방법은 가능한 모든 부분 배열을 일일이 살펴보면서 각 구간의 합이 0이 되는지 확인하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)로, 배열의 크기가 커지면 비효율적입니다.
2. 해싱(Hashing)을 활용한 효율적인 접근
훨씬 효율적인 방법은 해싱과 누적 합(prefix sum)을 활용하는 것입니다. 원리는 다음과 같습니다.
배열을 순회하면서 현재 인덱스까지의 누적 합을 계산하고, 이 값을 해시 테이블(집합)에 저장합니다.
순회 도중 다음 두 가지 조건 중 하나라도 만족하면 합이 0인 부분 배열이 존재한다는 뜻입니다.
- 현재까지의 누적 합이 정확히 0인 경우 → 처음부터 현재 인덱스까지의 구간 합이 0
- 동일한 누적 합이 이전에 이미 등장한 경우 → 두 등장 지점 사이의 부분 배열 합이 0
조건을 만족하는 부분 배열을 찾으면 true를 반환하고, 배열 전체를 순회해도 찾지 못하면 false를 반환합니다.
이 방법은 해시 집합의 삽입과 탐색이 평균 O(1)이므로 전체 시간 복잡도가 O(n)으로 크게 개선됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
bool isSubArraySumZero(int arr[], int n) {
// 누적 합을 저장할 해시 집합
unordered_set<int> sumHash;
int currSum = 0;
for (int i = 0 ; i < n ; i++) {
currSum += arr[i];
// 누적 합이 0이거나 이전에 동일한 값이 있으면 합이 0인 부분 배열 존재
if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
return true;
sumHash.insert(currSum);
}
return false;
}
int main() {
int arr[] = { 3, 1, -2, 1, 4, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
if (isSubArraySumZero(arr, n))
cout<<"SubArray with sum equal to 0 exists in the array";
else
cout<<"No subarray exists";
return 0;
}출력 결과
SubArray with sum equal to 0 exists in the array
마무리
합이 0인 부분 배열 문제는 누적 합과 해시 자료구조를 결합하면 선형 시간에 해결할 수 있는 대표적인 알고리즘 문제입니다. 같은 원리는 '특정 합 K를 가지는 부분 배열 찾기' 같은 변형 문제에도 그대로 응용할 수 있으므로, 개념을 잘 익혀두면 코딩 테스트에서 큰 도움이 됩니다.