크기가 10만 개가 넘는 거대한 수열(배열)이 주어지고, "이 배열 안에서 연속된 숫자들을 더했을 때, 그 합이 정확히 M이 되는 구간은 총 몇 개나 있을까?" 혹은 "합이 M 이상이 되는 연속 구간 중 길이가 가장 짧은 구간은 얼마인가?"라는 질문을 던졌을 때, 이중 반복문을 겹쳐 쓰는 O(N^2)의 낡은 무기를 꺼내 든다면 즉시 시간 초과(TLE)의 철퇴를 맞게 됩니다. 우리는 배열 전체를 단 한 번만 처음부터 끝까지 스캔하면서(O(N)), 마치 자벌레가 기어가듯 탐색 구간을 고무줄처럼 늘렸다 줄였다 하며 정답을 낚아채는 고급 기법을 사용해야만 합니다. 바로 '투 포인터(Two Pointers)' 알고리즘입니다. 오늘 이 글에서는 투 포인터를 이용해 연속 부분합 문제를 격파하는 핵심 논리와, "배열에 음수(-)가 섞여 있을 때" 투 포인터가 속수무책으로 박살 나는 치명적 이유와 그 극복 방안을 완벽하게 해부해 보겠습니다.
1. 자벌레의 이동: 투 포인터의 기본 원리
투 포인터로 연속된 부분합을 구할 때는 보통 start와 end라는 두 개의 화살표(인덱스 변수)를 배열의 맨 앞(0번 인덱스)에 나란히 두고 출발시킵니다. 현재 두 포인터 사이에 둘러싸인 숫자들의 누적 합을 sum이라고 할 때, 세 가지 절대 규칙에 따라 포인터를 움직입니다.
1-1. O(N) 탐색을 위한 3대 이동 규칙
- 현재 합(sum)이 타겟(M)보다 작을 때:
합을 더 키워야 하므로,end포인터를 오른쪽으로 한 칸 밀어서(++) 새로운 데이터를 구간에 포함시킵니다. (이동 후 sum += arr[end]) - 현재 합(sum)이 타겟(M)보다 클 때:
구간 안에 숫자가 너무 많이 들어와 합이 뚱뚱해진 상태입니다. 합을 깎아내려야 하므로,start포인터를 오른쪽으로 한 칸 밀어서(++) 맨 앞의 데이터를 구간에서 내뱉습니다. (이동 전 sum -= arr[start]) - 현재 합(sum)이 타겟(M)과 정확히 같을 때:
빙고! 정답을 하나 찾았습니다. 카운트를 +1 증가시킵니다. 그리고 다른 정답 구간을 더 찾기 위해,start포인터를 한 칸 밀어서 기존의 정답을 깨버리고 다음 탐색을 강제로 속행시킵니다.
이 논리를 while (end < N) 루프 안에 넣어 돌리면, start와 end 포인터는 뒤로 후진하는 법 없이 오직 오른쪽으로만 전진하므로 최대 2N번의 연산만 수행하게 됩니다. 결과적으로 O(N)의 경이로운 선형 시간 안에 모든 정답 구간을 완벽히 찾아냅니다.
2. 치명적인 함정: "음수(Negative)"가 섞여 있다면?
투 포인터 로직은 완벽해 보이지만, 문제의 조건에 "배열에 음수(-)가 포함될 수 있다"는 단 한 줄이 추가되는 순간 완전히 무너져 내립니다. 그 이유는 투 포인터가 기반하고 있는 '단조 증가성(Monotonicity)'이라는 수학적 전제가 산산조각 나기 때문입니다.
2-1. 단조 증가성의 붕괴
배열의 모든 숫자가 양수(자연수)라면, end 포인터를 오른쪽으로 밀어서 숫자를 구간에 넣을 때마다 전체 합(sum)은 무조건 커지거나 같아집니다(절대 작아지지 않음). 합이 커진다는 확실한 믿음이 있기 때문에 포인터를 조작할 수 있는 것입니다.
하지만 [-3, 5, -2, 7]처럼 음수가 끼어있다면 어떨까요? end를 밀어서 새로운 숫자를 구간에 넣었는데, 그 숫자가 -20이라면 오히려 합이 곤두박질치게 됩니다. "합이 작으니 end를 밀어 넣자!"라고 행동했는데 합이 더 작아져 버리는 모순에 빠집니다. 포인터는 길을 잃고 영원히 정답을 지나치게 됩니다.
3. 음수 함정의 극복: 누적 합(Prefix Sum) + 해시맵(HashMap)
배열에 음수가 끼어 있어 투 포인터를 쓸 수 없다면, 우리는 누적 합 배열과 해시 테이블을 결합한 수학적 접근으로 노선을 변경해야 합니다.
- 0번부터 i번까지의 누적 합을
prefix[i]라고 부릅니다. - 우리가 찾고자 하는 특정 구간
[j, i]의 합은prefix[i] - prefix[j-1]로 완벽히 치환됩니다. - 이 식이 타겟 M과 같아야 하므로,
prefix[i] - prefix[j-1] = M이 성립해야 합니다. - 식을 살짝 비틀면
prefix[j-1] = prefix[i] - M이 됩니다.
이 수식의 의미는 엄청납니다! 배열을 처음부터 훑으며 현재의 누적 합(prefix[i])을 구한 뒤, 과거에 계산했던 누적 합들 중에서 값이 prefix[i] - M과 정확히 일치하는 녀석이 있었는지 해시맵(HashMap)에서 단번에 O(1)로 조회하기만 하면 됩니다. HashMap<누적합 값, 등장 횟수>를 사용하여 데이터를 갱신해 나가면, 음수가 수만 개 섞여 있어도 O(N)의 시간으로 100% 완벽하게 정답 구간의 개수를 카운팅해 낼 수 있습니다. 이는 대기업 코딩 테스트에서 지원자의 한계를 테스트하는 최고 난이도의 단골 킬러 패턴입니다.
1. 투 포인터(Two Pointers)는
start와 end 두 개의 화살표를 조건에 따라 조작하여, 배열 내 연속된 부분합 구간을 O(N^2)에서 O(N)으로 획기적으로 찾아내는 탐색 기법입니다.2. 데이터 추가 시 합이 무조건 커진다는 단조 증가성을 맹신하므로, 배열에 음수(-)가 단 하나라도 섞여 있다면 포인터의 이동 논리가 박살 나며 투 포인터를 사용할 수 없게 됩니다.
3. 음수가 포함된 연속 부분합 문제는 투 포인터를 포기하고, 수학 공식인
prefix[j-1] = prefix[i] - 타겟을 활용한 누적 합(Prefix Sum)과 해시맵(HashMap)의 결합을 통해 O(N)으로 완벽하게 우회하여 풀어야 합니다.