투포인터: 양끝·같은방향

한 줄 정의

배열(또는 문자열)에 인덱스 두 개를 두고, 조건을 보며 한쪽·양쪽을 이동합니다.
정렬되어 있거나, 구간이 단조적으로 넓어/좁아질 때 특히 강력합니다.

패턴 A: 양끝에서 좁히기

회문, 두 수의 합(정렬 배열), 컨테이너에 물 등이 전형입니다.

function isPalindrome(s) {
  let lo = 0, hi = s.length - 1;
  while (lo < hi) {
    if (s[lo] !== s[hi]) return false;
    lo++;
    hi--;
  }
  return true;
}

def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

왜 빠른가: 각 원소를 최대 한 번만 방문 → O(n). 정렬이 필요하면 + O(n log n).

패턴 B: 같은 방향 (느린·빠른 / 좌·우 끝단)

• 연결리스트 사이클: 느린+빠른 포인터
• 중복 제거·파티션: 쓸 위치 w와 읽는 위치 r

// 0이 아닌 값을 앞으로 안정적으로 모으기 (개념)
let w = 0;
for (let r = 0; r < a.length; r++) {
  if (a[r] !== 0) {
    a[w++] = a[r];
  }
}

패턴 C: 구간을 넓히며 (슬라이딩과 경계)

투포인터와 슬라이딩 윈도우는 친척입니다.
오른쪽을 늘리고, 조건이 깨지면 왼쪽을 줄입니다. 슬라이딩 윈도우 레슨에서 깊게 다룹니다.

언제 쓰나 (신호)

• “연속 구간”, “양 끝”, “정렬된 배열에서 합”
• n이 커서 O(n²) 이중 루프가 불가능
• 구간에 원소를 더하면 합/개수가 단조 증가

함정

1. 정렬을 잊음 · 두 수의 합 양끝 패턴은 정렬 전제
2. 인덱스 교차 · lo < hi vs lo <= hi를 손으로 확인
3. 중복 값 · 같은 답을 여러 번 세지 않게 lo++/hi--를 건너뛰기
4. 빈 배열·길이 1 · 루프에 들어가기 전 처리

복잡도

연습 순서

1. 회문 검사 (양끝)
2. 정렬 배열 두 수의 합
3. 같은 방향 쓰기 포인터로 압축

막히면 작은 배열을 종이에 적고 lo/hi를 매 스텝 쓰세요. 예제 추적 사고 레슨과 같이 하면 효과가 큽니다.