두 포인터 (Two Pointer)

정의

두 포인터 (Two Pointer) 는 정렬 또는 단조 구조 에서 두 인덱스 l, r 을 서로 다른 속도 / 방향 으로 이동시키며 부분 구간 / 페어를 O(N) 에 탐색하는 기법.

슬라이딩 윈도우 는 두 포인터의 특수형 (두 포인터가 모두 앞으로만 이동). 누적 합 과 함께 N · Q 를 N + Q 또는 N 으로 떨어뜨리는 핵심 패턴.

문제 상황과 동기

“정렬된 두 배열에서 합이 target 인 페어가 몇 개?” / “부분 배열 중 합이 ≤ K 인 것의 최대 길이?”

• naive: 모든 페어 / 모든 부분 배열. O(N²).
• two pointer: 두 인덱스의 이동이 총 O(N). 한 번 방문한 인덱스는 다시 방문 안 함 (amortized).

핵심 통찰: l 을 늘리거나 r 을 늘려도 답이 단조 라면, 둘 중 한 방향만 항상 움직이면 전체 O(N).

시각화

핵심 아이디어

패턴 A: 양 끝에서 좁히기 (정렬된 배열의 합)

정렬된 a, target T
l = 0, r = N - 1
while l < r:
    s = a[l] + a[r]
    if s == T:     찾음, l++, r--
    elif s < T:    l++              // 더 큰 합 필요
    else:          r--              // 더 작은 합 필요

l 과 r 은 각각 한 방향으로만 이동. 총 N 이동. O(N).

패턴 B: 같은 방향 슬라이딩 (sliding window)

부분 배열 합 ≤ K 의 최대 길이
l = 0, sum = 0, best = 0
for r in 0..N-1:
    sum += a[r]
    while sum > K:
        sum -= a[l]
        l++
    best = max(best, r - l + 1)

r 은 매 단계 +1. l 은 때때로 +1 (총 ≤ N 번). 결국 amortized O(N).

패턴 C: 두 정렬된 배열 머지

두 정렬된 a, b 의 교집합 / 합집합 / 차집합
i = j = 0
while i < |a| and j < |b|:
    if a[i] < b[j]: ... ; i++
    elif a[i] > b[j]: ... ; j++
    else: ... ; i++; j++

머지 정렬 의 merge 단계와 동일. O(|a| + |b|).

알고리즘

two_pointer(a, target):       # 패턴 A: 합 = target 페어 카운트
    sort(a)
    l = 0, r = N - 1
    cnt = 0
    while l < r:
        s = a[l] + a[r]
        if s == target:
            cnt++
            l++, r--
        elif s < target:  l++
        else:             r--
    return cnt

구현

// 정렬된 배열에서 두 수의 합 = target 인 페어 개수 (O(N))
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; long long t;
  cin >> n >> t;
  vector<long long> a(n);
  for (auto& v : a) cin >> v;
  sort(a.begin(), a.end());
  int l = 0, r = n - 1, cnt = 0;
  while (l < r) {
      long long s = a[l] + a[r];
      if (s == t) { cnt++; l++; r--; }
      else if (s < t) l++;
      else            r--;
  }
  cout << cnt << "\n";
}

# 정렬된 배열에서 두 수의 합 = target 페어 개수
import sys
input = sys.stdin.readline
​
n, t = map(int, input().split())
a = sorted(map(int, input().split()))
l, r = 0, n - 1
cnt = 0
while l < r:
  s = a[l] + a[r]
  if s == t:
      cnt += 1
      l += 1; r -= 1
  elif s < t:
      l += 1
  else:
      r -= 1
print(cnt)

// 정렬된 배열에서 두 수의 합 = target 페어 개수
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      long t = Long.parseLong(st.nextToken());
      long[] a = new long[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++)
          a[i] = Long.parseLong(st.nextToken());
      Arrays.sort(a);
      int l = 0, r = n - 1, cnt = 0;
      while (l < r) {
          long s = a[l] + a[r];
          if (s == t) { cnt++; l++; r--; }
          else if (s < t) l++;
          else            r--;
      }
      System.out.println(cnt);
  }
}

6 10
1 2 3 7 8 9

3

5 6
1 2 3 3 5

2

(예제 1: 1+9, 2+8, 3+7 의 3 페어. 예제 2: 1+5, 3+3 의 2 페어)

복잡도

변형 / 활용

• 부분 합 = K 개수: 누적합 + 두 포인터 (음수 없는 경우만)
• 부분 곱 ≤ K: 곱셈 인수가 양수일 때
• Three sum / k sum: 한 인덱스 고정 + two pointer (한 차원 줄임)
• 단조 큐 / 단조 스택: 슬라이딩 윈도우의 max/min 유지
• 머지 정렬의 merge 단계: 자연스러운 두 포인터

함정

1. 정렬 / 단조 조건

값에 단조성 이 있어야 두 포인터가 가능. 임의 순서 입력은 정렬 후 사용.

2. 같은 페어 중복 카운트

(l, r) 과 (r, l) 을 둘 다 세지 않도록 l < r 유지.

3. 같은 값 중복 처리

정렬 후 같은 값이 여러 개면 페어 카운트가 더 복잡 (조합 수). 그룹 별 카운트 후 곱셈.

4. 음수 합 / 0

음수가 섞이면 부분 배열 합 의 단조성이 깨져 슬라이딩 윈도우 사용 불가. 대신 누적합 + 해시.

BOJ 연습 문제

참고

• 슬라이딩 윈도우
• 누적 합
• 이분 탐색
• 머지 정렬