투 포인터 언제 쓰나, 음수·0 입력 판단표와 슬라이딩 윈도우 버그 점검

배열 문제를 보고 "이거 투 포인터로 되겠다" 싶어서 짰는데 예제는 맞고 제출하면 틀리거나, 반대로 투 포인터로 될 문제를 해시맵으로 풀다 메모리가 빠듯해진 적 있으시죠? 결론부터 말하면 투 포인터를 쓸지는 문제 유형이 아니라 입력 조건 세 가지로 정해요. 정렬돼 있나(또는 정렬해도 되나), 원소에 음수가 있나, 그리고 "정확히 x인 개수"를 세는데 0이 섞여 있나. 음수가 하나라도 있으면 구간 합 문제는 누적합 + 해시맵으로 가고, 0만 있으면 "x 이하 개수" 두 번의 차로 투 포인터를 살릴 수 있어요.

이 글은 원리 증명보다 고르는 기준과 숫자를 다뤄요. 제약 조건은 CSES 문제 페이지에서 확인했고(2026-10-26), 시간·메모리는 Apple M1, 파이썬 3.13.7과 Apple clang 17(-O2)로 직접 쟀어요. 절대 시간은 기기마다 다르니 방식 사이의 배수로 읽어 주세요.

먼저 가를 것, 입력 조건 판단표

투 포인터 계열은 "포인터를 한 방향으로만 움직여도 답을 놓치지 않는다"는 전제 위에서만 맞아요. 이 전제는 입력 조건이 만들어 줘요. 그래서 기법보다 조건을 먼저 확인해요.

마지막에서 둘째 줄처럼 합이 아닌 조건도 단조이면 윈도우가 돼요. "서로 다른 값의 개수"는 구간을 넓히면 줄지 않고 좁히면 늘지 않으니, 원소 값에 음수가 있든 없든 상관없어요. CSES 2428 "Subarray Distinct Values"가 이 꼴이에요. 반대로 합 조건은 값의 부호에 따라 단조성이 생기기도 하고 사라지기도 해요.

CSES 제약으로 보는 입력 조건 확인법

제약 한 줄이 기법을 바꾸는 경우가 많아요.

• CSES 1660 Subarray Sums I: "n개의 양의 정수", 1 ≤ x, aᵢ ≤ 10⁹. 슬라이딩 윈도우가 맞아요.
• CSES 1661 Subarray Sums II: "n개의 정수", −10⁹ ≤ x, aᵢ ≤ 10⁹. 같은 질문인데 음수가 있어 누적합 + 해시맵이에요.
• CSES 1640 Sum of Two Values: 정렬되지 않은 배열에서 "서로 다른 위치"의 두 값, 원래 위치를 출력해요. 정렬하려면 위치를 같이 들고 가야 해요.

세 문제 모두 n ≤ 2×10⁵, 시간 제한 1초예요. 실무 데이터도 똑같이 봐요. 금액 차액·온도 변화량·재고 증감처럼 차이값 열은 음수가 섞이는 게 정상이고, 요청 수·바이트 수·처리 시간처럼 양으로만 쌓이는 값은 0이 섞이는 게 정상이에요. 스키마나 API 문서에서 "0 이상인지, 양수인지"를 먼저 확인하는 이유예요.

n 크기별 시간 예산 직접 계산, 이중 반복문은 어디까지 되나

"투 포인터를 꼭 써야 하나, 이중 반복문으로 되지 않나"는 n으로 정해요. 답이 없는 최악의 경우(모든 쌍을 다 봄)로 이중 반복문의 쌍 하나당 시간을 쟀어요.

• C++ -O2: n=2만(쌍 약 2억 개)에 약 160ms → 쌍 하나 약 0.8ns
• 파이썬: n=8,000(쌍 약 3,200만 개)에 약 7.7초 → 쌍 하나 약 240ns

이 단가로 n별 시간을 추산하면 이래요. 쌍 수는 n(n−1)/2 예요.

C++는 n이 몇만까지는 이중 반복문도 1초 안이에요. CSES 1641 "Sum of Three Values"가 n ≤ 5,000으로 잡혀 있는 것도 이 때문이에요. 하나를 고정하고 안쪽을 투 포인터로 돌리는 O(n²)이 약 1,250만 단계라 넉넉해요. 반면 n=20만이면 언어와 상관없이 이중 반복문은 안 되고, O(n)이나 O(n log n)으로 가야 해요.

같은 n=20만에서 O(n) 계열끼리는 이렇게 나왔어요(파이썬, 다섯 번 중 최솟값).

파이썬에서 쌍 찾기는 해시맵이 더 빨라요. 투 포인터 자체는 O(n)이지만 원래 위치를 들고 정렬하는 데 시간이 대부분 들어가요. 정렬 비용이 key 함수에 따라 얼마나 달라지는지는 파이썬·자바 정렬 성능 판단표에 따로 재 두었어요. 투 포인터가 확실히 이기는 건 입력이 이미 정렬돼 있을 때(DB에서 ORDER BY로 받은 결과, 시간순 로그)와 메모리가 빠듯할 때예요.

메모리 비용 계산, 누적합 + 해시맵은 얼마나 드나

음수 때문에 누적합 + 해시맵으로 바꾸면 시간은 비슷해도 메모리가 n에 비례해 늘어요. 파이썬 tracemalloc으로 최대 사용량을 쟀어요.

누적합이 서로 다르면 딕셔너리 항목이 n+1개 생기고, 파이썬은 큰 정수 객체와 해시 테이블 여유 공간까지 들어서 항목 하나에 200바이트 안팎이 들어요. 메모리 제한이 512MB인 CSES에선 문제가 없지만, 서버에서 수천만 건 스트림에 이 방식을 쓰면 이 크기가 그대로 RSS가 돼요. 그래서 원소가 0 이상이 보장되면 아래의 "x 이하 차이"로 O(1) 메모리를 지키는 쪽이 나아요.

0이 섞인 정확히 x 개수, x 이하 두 번의 차로 고치기

원소에 0이 섞이면 단순 윈도우("넘치면 left를 밀고, 같으면 1 더함")가 개수를 덜 세요. 앞쪽 0을 빼도 합이 그대로라서 같은 right에 맞는 시작점이 여러 개 생기는데, 윈도우는 그중 하나만 보기 때문이에요. 0~4 범위의 무작위 배열 5,000개로 돌려 보니 1,378개(약 28%)에서 답이 틀렸어요. 예제에 0이 없으면 테스트를 통과해서 더 위험해요.

고치는 방법은 질문을 바꾸는 거예요. "합이 정확히 x인 구간 수"는 "합이 x 이하인 구간 수 − 합이 x−1 이하인 구간 수"와 같아요. 그리고 "합이 x 이하"는 원소가 0 이상이면 단조라서 윈도우로 정확히 셀 수 있어요. right마다 [left, right] 안의 모든 시작점이 조건을 만족하니 right − left + 1을 더하면 돼요.

def at_most(a, x):          # 합 <= x 인 구간 수, 원소는 0 이상
    if x < 0:
        return 0
    cnt = tot = left = 0
    for right, v in enumerate(a):
        tot += v
        while tot > x:
            tot -= a[left]
            left += 1
        cnt += right - left + 1
    return cnt

def exact(a, x):
    return at_most(a, x) - at_most(a, x - 1)

print(exact([0, 0, 3, 0], 3))   # 6

[0, 0, 3, 0]에서 합이 3인 구간은 6개인데, 단순 윈도우는 2를 돌려줬어요. 위 exact는 전수 탐색과 5,000번 대조해 모두 맞았어요. 같은 요령이 "서로 다른 값이 정확히 k개인 구간 수"에도 그대로 통해요(k개 이하 − k−1개 이하). 이 방법은 정수 값일 때만 x−1이 "x 바로 아래"라는 뜻이 돼요. 실수 합이면 쓰지 말고 누적합 쪽으로 가요.

실무에서 쓰는 자리, 시간 창과 정렬된 목록

투 포인터는 코딩 테스트 밖에서도 자주 쓰여요. 다만 실무에선 "직접 짤지, 이미 있는 것을 쓸지"가 먼저예요.

최근 N초 시간 창. "최근 60초 요청 수"처럼 시간 창 집계는 슬라이딩 윈도우 그대로예요. 시각은 늘기만 하니 단조성이 자동으로 생겨요. 덱(deque)에 시각을 넣고 앞에서 오래된 것을 빼면 돼요. 파이썬 collections 문서는 deque의 양끝 넣기·빼기가 양쪽 모두 대략 O(1)이라고 적어요. 함정은 도착 순서가 시간 순서가 아닐 때예요. 여러 서버 로그를 합치면 늦게 온 이벤트가 이미 지나간 창에 속할 수 있어, 정렬해 일괄 처리하거나 초 단위 버킷으로 바꿔요. 시각을 숫자로 다룰 때 초와 밀리초가 섞이면 창 크기가 1,000배 틀어지니 초·밀리초 혼동 버그도 같이 확인해요.

정렬된 두 목록 비교. 두 시스템의 ID 목록을 맞춰 보는 대사(reconciliation) 작업은 정렬된 두 목록을 두 포인터로 걷는 병합이에요. 그런데 파이썬에서는 직접 짠 루프가 내장 집합 연산보다 느렸어요.

파이썬 반복문 한 바퀴가 C로 짠 내장 함수 한 단계보다 훨씬 비싸서, 복잡도가 같거나 더 좋아도 직접 짠 쪽이 느릴 수 있어요. 직접 짤 이유는 입력이 너무 커서 집합을 만들 메모리가 없을 때(파일 두 개를 한 줄씩 스트리밍으로 비교)와 C++·Go·자바처럼 반복문이 싼 언어일 때예요. 몇 천 줄짜리 목록을 한 번 정리하는 정도면 텍스트 줄 정렬기로 정렬하고 텍스트 중복 제거로 걸러도 충분해요.

연속 중복 제거. 읽기·쓰기 포인터는 표준 라이브러리에 이미 있어요. C++ std::unique와 Go slices.Compact는 둘 다 연속한 같은 값만 하나로 줄여서, 정렬하지 않은 데이터에선 떨어져 있는 중복이 남아요. 동작 차이도 알아 둬요.

cppreference는 std::unique 뒤 남은 구간 원소가 "유효하지만 지정되지 않은 상태"라고 적어요. erase를 빠뜨리면 컨테이너 크기가 그대로라 뒤쪽 쓰레기 값을 그대로 쓰게 돼요. Go는 Go 1.22 릴리스 노트대로 줄어든 뒤 칸을 0 값으로 비워서, 포인터를 담은 원소가 메모리에 붙잡혀 있지 않아요.

운영에서 자주 나는 문제와 확인 순서, 체크리스트

투 포인터 버그는 대부분 예외 없이 조용히 틀린 개수를 내요. 그래서 확인 순서를 정해 두는 게 빨라요.

1. 입력 부호와 정렬. 음수가 가능한지, 이미 정렬돼 있는지를 문서에서 확인해요. "정렬돼 들어온다"는 가정은 데이터 원천이 바뀌면 깨져요. 테스트에서만 정렬 여부를 검사하고, 운영 코드에 매번 넣으면 O(n)이 추가돼요.
2. 정확히 x 개수인데 0이 있는지. 있으면 단순 윈도우를 x 이하 두 번의 차로 바꿔요.
3. 합과 개수의 정수 폭. n=20만, 원소 최대 10⁹이면 구간 합 최대가 2×10¹⁴, 구간 개수 최대가 n(n+1)/2 = 20,000,100,000이에요. 32비트 int 최대 2,147,483,647을 둘 다 넘어요. C++에서 int로 10⁹를 세 번 더하면 −1,294,967,296이 찍혔어요. 합·개수·누적합 맵 키 모두 long long·long·int64로 둬요. 음수가 왜 나오는지는 2의 보수로 보면 바로 보여요(2진수·16진수 변환 원리).
4. 포인터 되감기와 경계. right마다 left = 0으로 되돌리면 O(n²)으로 돌아가요. 마주 보는 포인터의 반복 조건은 i < j예요. i <= j면 같은 원소를 두 번 쓴 답이 나와요. 윈도우를 닫힌 구간 [left, right]로 쓸지 반열린 구간으로 쓸지 하나로 정해요.
5. 정렬 뒤 원래 위치. CSES 1640처럼 위치를 내야 하면 (값, 위치) 쌍으로 정렬해요. 값만 정렬하면 출력 위치가 틀려요. 3Sum류에서 같은 값을 고정점으로 다시 돌지 않게 건너뛰는 것도 여기서 확인해요.

고친 뒤엔 작은 무작위 입력으로 전수 탐색과 대조해요. 값 범위를 0~4처럼 좁혀 0과 중복이 자주 나오게 하고, 음수가 가능하다면 −3~3처럼 부호를 섞어요.

import random

def brute(a, x):
    return sum(sum(a[l:r + 1]) == x
               for l in range(len(a)) for r in range(l, len(a)))

for _ in range(5000):
    a = [random.randint(0, 4) for _ in range(random.randint(1, 12))]
    x = random.randint(0, 10)
    assert exact(a, x) == brute(a, x), (a, x)

도입 전에 따질 것

직접 투 포인터를 짜기 전에 아래를 확인해요.

• n과 언어: 위 표대로 C++에서 n이 몇만 이하면 이중 반복문도 돼요. 읽기 쉬운 코드가 유지보수에 더 싸다면 그쪽을 고를 수도 있어요.
• 정렬 상태의 출처: DB ORDER BY나 시간순 로그처럼 정렬이 공짜로 오면 투 포인터가 가장 싸요. 정렬을 새로 해야 하면 파이썬에선 해시맵이 더 빨랐어요.
• 값의 부호 보장: "0 이상"인지 "양수"인지가 스키마·검증 로직으로 보장되는지 봐요. 보장이 약하면 누적합 + 해시맵이 안전해요. 메모리는 n=100만에서 파이썬 기준 약 165MiB였어요.
• 도착 순서: 시간 창 집계라면 늦게 오는 이벤트가 있는지, 있다면 얼마나 늦는지 먼저 재요.
• 이미 있는 구현: 중복 제거·병합·교집합은 표준 라이브러리나 DB 쿼리로 끝나는 경우가 많아요.

자주 묻는 질문

슬라이딩 윈도우는 음수가 있으면 무조건 못 쓰나요?

합 조건이라면 못 써요. 음수를 빼면 합이 오히려 커져서 "넘치면 left를 민다"가 틀리기 때문이에요. 다만 "서로 다른 값 k개 이하"처럼 값의 부호와 무관하게 단조인 조건이면 음수가 있어도 윈도우가 맞아요. 음수가 섞인 구간 합 개수는 누적합 + 해시맵으로 풀어요.

원소에 0이 있으면 슬라이딩 윈도우가 틀리나요?

"합이 x 이하인 최장 구간"처럼 이하 조건은 0이 있어도 맞아요. 틀리는 건 "합이 정확히 x인 구간 개수"예요. 이때는 at_most(x) − at_most(x−1)로 바꾸면 O(n), O(1) 메모리로 정확히 셀 수 있어요.

두 수의 합은 투 포인터와 해시맵 중 무엇이 낫나요?

이미 정렬돼 있으면 투 포인터가 메모리 O(1)로 가장 싸요. 정렬이 안 돼 있으면 파이썬 측정에서 해시맵이 약 2.8배 빨랐어요(n=20만, 140ms 대 399ms). 원래 위치가 필요하면 해시맵이 위치를 그대로 들고 있어 더 단순해요.

투 포인터 코드에 while이 두 겹인데 시간 초과가 날까요?

안쪽 while이 left를 한 칸씩 앞으로만 옮기면 전체 이동이 n번을 넘지 못해 O(n)이에요. 시간 초과가 난다면 right마다 left를 처음으로 되돌리는 코드가 있는지, 안쪽에서 구간 합을 매번 새로 더하고 있는지 확인해요.

구간 합 결과가 음수로 나와요.

32비트 정수 오버플로일 가능성이 커요. n=20만, 원소 10⁹이면 합이 2×10¹⁴까지 가요. 합·개수·누적합을 모두 64비트 정수로 바꿔요. 파이썬은 정수 크기 제한이 없어 이 문제가 없어요.

실무 데이터에도 투 포인터를 직접 짜야 하나요?

시간순 로그의 최근 N초 집계나, 메모리에 다 못 올리는 두 정렬 파일 비교라면 직접 짜는 게 맞아요. 메모리에 들어가는 크기라면 파이썬에선 내장 set 연산이나 itertools.groupby가 직접 짠 루프보다 빨랐어요.

정리

• 기법은 입력 조건으로 골라요. 정렬된 쌍은 마주 보는 포인터, 양수 구간 합은 윈도우, 0 이상의 정확히 x 개수는 x 이하 두 번의 차, 음수가 있으면 누적합 + 해시맵이에요.
• n=20만이면 이중 반복문은 C++로도 약 16초라 안 돼요. O(n) 계열끼리는 시간보다 메모리(해시맵 n=20만 약 41MiB)와 정렬 비용이 갈라요.
• 합·개수는 64비트로, 테스트는 0과 음수가 자주 나오는 좁은 값 범위의 무작위 대조로 해요.
• 경계 버그가 비슷한 이분 탐색은 이분 탐색 판단표와 경계 버그 체크리스트에서 같은 방식으로 정리해 두었어요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 투 포인터 원리 — 왜 O(n)인가, 음수에서 깨지는 이유에서 도식과 코드로 단계별로 풀었어요.