투 포인터 (슬라이딩 윈도우, 부분합, 시간복잡도)
"연속한 부분 배열 중 합이 가장 큰 것", "합이 정확히 K인 구간의 개수", "중복 없는 가장 긴 부분 문자열" — 이런 문제를 만나면 초보자는 본능적으로 이중 반복문을 떠올린다. 모든 시작점과 끝점을 다 시도하면 O(N²)이다. 그러나 배열을 한 번만 훑으면서 두 개의 포인터를 적절히 움직이면 같은 문제를 O(N)에 풀 수 있다. 이것이 투 포인터(Two Pointer)와 그 특수형인 슬라이딩 윈도우(Sliding Window)다. 본 글은 두 기법의 동작 원리, 고정 크기와 가변 크기 윈도우의 차이, 그리고 단조성이라는 적용 조건을 세심하게 정리한다(출처: 위키백과 — Maximum subarray problem). 제가 코딩 테스트를 처음 준비할 때 O(N²) 풀이로 시간 초과를 연달아 받다가, 투 포인터로 같은 문제가 한 줄짜리 반복문으로 줄어드는 경험을 한 뒤로는 "반복문을 두 개 겹치기 전에 포인터 두 개로 풀 수 없는지 먼저 묻는다"는 습관이 생겼다.
투 포인터의 기본 원리
투 포인터는 배열 위에 두 개의 인덱스를 두고, 조건에 따라 둘을 각각 전진시키며 답을 찾는 기법이다. 가장 전형적인 형태는 정렬된 배열에서 합이 목표값 K인 두 원소 찾기다. 한 포인터는 왼쪽 끝, 다른 포인터는 오른쪽 끝에서 시작해 서로를 향해 좁혀 온다.
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
return (left, right)
elif s < target:
left += 1 # 합이 작다 → 왼쪽을 키워 합 증가
else:
right -= 1 # 합이 크다 → 오른쪽을 줄여 합 감소
return None이 풀이가 O(N)인 이유는 두 포인터가 각각 한 방향으로만 움직여 만나면 끝나기 때문이다. 핵심은 합이 작으면 왼쪽을, 크면 오른쪽을 움직인다는 결정이 항상 올바르다는 점인데, 이는 배열이 정렬되어 있어 "왼쪽을 키우면 합이 단조 증가한다"는 단조성이 보장되기 때문이다. 정렬되지 않은 배열에는 이 기법을 그대로 쓸 수 없고, 이 경우 해시 테이블로 O(N) 풀이를 만들어야 한다는 점이 두 접근의 갈림길이다.
슬라이딩 윈도우 — 연속 구간의 특수형
슬라이딩 윈도우는 투 포인터의 특수형으로, 두 포인터가 연속한 구간(window)의 양 끝을 가리키며 그 창을 오른쪽으로 밀어 가는 형태다. 창이 한 칸 이동할 때 빠지는 원소와 들어오는 원소만 계산에 반영하므로, 매번 구간 합을 처음부터 다시 구하는 낭비를 없앤다. 고정 크기 K짜리 부분 배열의 최대 합을 구하는 문제가 대표적이다.
def max_sum_window(arr, k):
window = sum(arr[:k]) # 첫 윈도우 합
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # 들어온 것 더하고 나간 것 뺌
best = max(best, window)
return best여기서 arr[i] - arr[i - k] 한 줄이 슬라이딩 윈도우의 정수다. 새로 들어온 arr[i]를 더하고 창에서 빠진 arr[i-k]를 빼는 것만으로 다음 창의 합을 O(1)에 갱신한다. 만약 이 갱신 없이 매 위치에서 창 전체를 다시 더했다면 O(N×K)가 되어 슬라이딩 윈도우의 의미가 사라진다(출처: GeeksforGeeks — Short Notes on Two Pointer and Sliding Window).
가변 크기 윈도우는 한층 더 강력하다. "합이 K 이하인 가장 긴 구간"처럼 창의 크기가 조건에 따라 늘었다 줄었다 하는 문제는, 오른쪽 포인터로 창을 넓히다가 조건을 위반하면 왼쪽 포인터로 창을 좁히는 방식으로 푼다.
def longest_at_most_k(arr, k): # 합이 k 이하인 최장 구간 길이
left, total, best = 0, 0, 0
for right in range(len(arr)):
total += arr[right] # 창 확장
while total > k: # 조건 위반 시 축소
total -= arr[left]
left += 1
best = max(best, right - left + 1)
return best이 코드에서 두 포인터가 각각 최대 N번씩만 전진하므로, 안쪽에 while이 있어도 전체는 O(N)이다. 이 "두 포인터가 합쳐 2N번 이동"이라는 분석이 슬라이딩 윈도우의 복잡도를 이해하는 열쇠이며, 처음에는 중첩 반복문처럼 보여 O(N²)로 착각하기 쉽다.
적용 조건과 한계 — 단조성이 핵심
투 포인터와 슬라이딩 윈도우가 강력하긴 하지만 아무 문제에나 쓸 수 있는 것은 아니다. 적용의 핵심 전제는 단조성이다. 슬라이딩 윈도우의 경우, 창을 넓히면 어떤 값(합·길이 등)이 한 방향으로만 변하고, 좁히면 반대 방향으로만 변해야 한다. 예컨대 원소에 음수가 섞이면 "창을 넓혔는데 합이 오히려 줄어드는" 비단조 상황이 생겨 가변 윈도우 논리가 깨진다. 이 경우 누적합(prefix sum)과 해시, 또는 다른 기법으로 우회해야 한다.
| 기법 | 전형 문제 | 시간복잡도 | 전제 조건 |
|---|---|---|---|
| 투 포인터(양끝) | 정렬 배열 두 수의 합 | O(N) | 배열 정렬됨 |
| 고정 슬라이딩 윈도우 | 크기 K 구간 최대합 | O(N) | 구간 길이 고정 |
| 가변 슬라이딩 윈도우 | 조건 만족 최장/최단 구간 | O(N) | 단조성 성립 |
| 누적합 + 해시 | 합이 K인 구간 개수 | O(N) | 음수 허용 |
흔한 오해 하나를 짚으면, "슬라이딩 윈도우는 모든 부분 배열 문제에 통한다"는 통념이다. 실제로는 음수가 섞인 합 문제나 구간 곱 문제 등 단조성이 깨지는 경우가 적지 않으며, 이때는 누적합과 해시맵 조합이 정석이다. 시험에서는 투 포인터가 단순 두 수의 합으로 출제되지만, 실무와 코딩 테스트의 중급 이상 문제에서는 가변 윈도우와 단조성 판단이 진짜 실력을 가른다. 솔직히 이 기법은 외워서 푸는 것이 아니라, "이 문제에 단조성이 있는가?"를 먼저 묻는 사고 습관을 들였을 때 비로소 손에 익는다.
메타 디스크립션: 이중 반복문 O(N²) 풀이를 O(N)으로 줄이는 투 포인터와 슬라이딩 윈도우의 동작 원리를, 고정·가변 크기 윈도우 코드 예시와 단조성이라는 적용 조건을 중심으로 코딩 테스트 입문자 관점에서 세심하게 정리합니다.