들어가며
코딩 테스트에서 연속된 구간(부분 수열) 관련 문제가 나오면, 우선 누적합이나 투포인터를 떠올리면 해결 가능성이 높습니다.
물론 문제를 "찍어서" 푸는 습관은 지양해야 하지만, 자주 등장하는 패턴을 먼저 인식하는 것은 매우 중요합니다.
이번 글에서는 투포인터를 사용하는 대표적인 두 가지 유형을 정리해보겠습니다.
1. 투포인터의 핵심
투포인터의 핵심은 단순합니다.
"현재 포인터가 가리키는 값이 앞으로도 정답이 될 수 있는가?"
이 질문에 대해 "아니다"라고 판단되는 값을 정답 후보군에서 제거해 나가는 방식이 바로 투포인터입니다.
즉, 포인터를 옮기는 행위는 단순한 이동이 아니라 정답 범위를 줄이는 과정입니다.
2. 유형 1: 조건을 만족하는 두 수 찾기
대표 문제: 백준 3273 - 두 수의 합
정렬된 배열에서 시작 포인터 s, 끝 포인터 e를 두고 탐색합니다.
핵심은 매 순간 arr[s]와 arr[e]의 합을 보고, 둘 중 누가 더 이상 정답이 될 수 없는지 판단하는 것입니다.
예를 들어 target = 13이고 배열이 아래와 같다고 가정해보겠습니다.
1 2 3 5 7 9 10 11 12
s e현재 합은 1 + 12 = 13이므로 정답입니다.
반대로 합이 target보다 큰 상황을 보겠습니다.
이때 흔히 "값이 크니까 e를 줄입니다"라고만 외우기 쉬운데, 정확한 근거는 다음과 같습니다.
e는 현재 배열에서 큰 값 쪽을 가리킵니다.- 이미 가장 작은 값(
arr[s])과 더해도 합이 크다면, e를 유지한 채 다른 값과 조합해도 정답이 될 수 없습니다.
즉, e가 가리키는 값 자체를 후보군에서 제외할 수 있으므로 e -= 1을 수행합니다.
while s < e:
curr = arr[s] + arr[e]
if curr > target:
e -= 1
elif curr == target:
answer += 1
# 문제 조건: 수가 서로 다름
s += 1
e -= 1
else:
s += 1핵심은 포인터를 움직이는 기준이 "감"이 아니라,
정답 후보 제거가 가능한지 여부라는 점입니다.
3. 유형 2: 조건을 만족하는 연속 구간 찾기
대표 문제: 백준 2003 - 수들의 합 2
이 유형에서는 보통 [s, e]를 하나의 윈도우로 보고 합을 관리합니다.
기본적인 완전 탐색은 아래처럼 O(N^2)입니다.
for i in range(n):
total = 0
for j in range(i, n):
total += arr[j]
if total == target:
answer += 1
if total > target:
break투포인터를 적용하면 s, e는 전체를 한 번씩만 지나가므로 O(N)으로 줄일 수 있습니다.
(arr의 원소가 자연수라는 조건이 있어야 이 방식이 성립합니다.)
s, e = 0, 0
total = arr[0] if n > 0 else 0
while s < n and e < n:
if total == target:
answer += 1
if total < target:
e += 1
if e >= n:
break
total += arr[e]
else:
total -= arr[s]
s += 14. 슬라이딩 윈도우와의 관계
실무/코테에서 종종 섞어 부르지만, 보통은 아래처럼 이해하면 편합니다.
- 투포인터: 포인터 2개를 두고 범위를 조절하는 큰 개념입니다.
- 슬라이딩 윈도우: 그중에서도 "구간"을 이동하며 값을 갱신하는 패턴입니다.
즉, 슬라이딩 윈도우는 투포인터의 대표적인 구현 패턴 중 하나라고 볼 수 있습니다.
마치며
투포인터는 "포인터를 어떻게 움직일까?"보다
"지금 어떤 값을 정답 후보에서 제외할 수 있는가?" 를 먼저 생각하면 훨씬 안정적으로 적용할 수 있습니다.