투 포인터

투 포인터란?

투 포인터(two pointers) 는 배열 위에 두 개의 인덱스(포인터) 를 두고, 둘을
적절히 움직여 \(O(N^2)\)로 보이는 문제를 \(O(N)\)에 푸는 기법입니다.

모든 쌍이나 모든 구간을 일일이 다 보는 대신, 이미 본 정보를 활용해 포인터를
한 방향으로만 전진시켜 중복 작업을 없앱니다.

1. 두 가지 큰 유형

• 같은 방향(슬라이딩): 두 포인터 l, r이 모두 왼쪽에서 오른쪽으로 이동.
  "조건을 만족하는 구간"을 찾을 때.
• 마주 보는 방향: l은 왼쪽 끝, r은 오른쪽 끝에서 가운데로 수렴.
  정렬된 배열에서 "합이 목표인 쌍" 등을 찾을 때.

문제 모양에 따라 둘 중 하나를 고릅니다.

2. 핵심 아이디어: 포인터를 되돌리지 않는다

투 포인터가 빠른 이유는 각 포인터가 전체 배열을 한 번씩만 지나가기 때문입니다.
\(l\)과 \(r\)이 각각 최대 \(N\)번 전진하므로 전체 \(O(N)\)입니다.

이것이 가능하려면 단조성이 필요합니다 — 예를 들어 "구간을 늘리면 합이
커진다"처럼, 포인터를 한 방향으로만 움직여도 답을 놓치지 않아야 합니다.

3. 예: 합이 목표인 구간 (양수 배열)

"연속한 부분 배열 중 합이 정확히 \(S\)인 것의 개수"를 구합니다.

l, r을 0에서 시작. 현재 구간 합을 들고:
- 합 < S 이면: r을 늘려 구간을 키운다.
- 합 >= S 이면: l을 늘려 구간을 줄인다.
- 합 == S 이면: 센다.

합이 너무 작으면 오른쪽으로 키우고, 너무 크면 왼쪽을 버린다 — 두 포인터가
앞으로만 가며 모든 유효 구간을 정확히 한 번씩 봅니다.

4. 예: 정렬된 배열에서 두 수의 합

정렬된 배열에서 합이 \(T\)인 쌍 찾기. 양 끝에서 시작:

l = 0, r = n-1
- a[l] + a[r] == T : 찾음
- a[l] + a[r] < T  : l++ (합을 키워야)
- a[l] + a[r] > T  : r-- (합을 줄여야)

정렬되어 있으니 합의 크기에 따라 어느 포인터를 움직일지 명확합니다.

5. 투 포인터 vs 슬라이딩 윈도우

둘은 매우 가깝습니다. 슬라이딩 윈도우는 투 포인터의 한 형태로, 보통 창 안의
정보(합·개수 등)를 유지하며 같은 방향으로 움직이는 경우를 부릅니다. 별도
주제로 더 다룹니다.

정리

투 포인터는 두 인덱스를 한 방향(또는 마주 보며)으로 움직여 \(O(N^2)\)를 \(O(N)\)으로
줄입니다. 핵심은 포인터를 되돌리지 않아도 되는 단조성입니다. "연속 구간",
"정렬된 배열의 쌍"이 보이면 떠올리세요. 다음 강의에서 구현합니다.

투 포인터를 코드로

대표 유형들을 구현하고, 단조성·경계 처리의 함정을 다룹니다.

1. 합이 목표인 연속 구간 개수 (양수 배열)

같은 방향 투 포인터. r로 키우고 l로 줄입니다.

int l = 0, cnt = 0;
long long sum = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];                       // 오른쪽 확장
    while (sum > target && l <= r) {   // 너무 크면 왼쪽 축소
        sum -= a[l++];
    }
    if (sum == target) cnt++;
}

l, cnt, s = 0, 0, 0
for r in range(n):
    s += a[r]
    while s > target and l <= r:
        s -= a[l]
        l += 1
    if s == target:
        cnt += 1

r은 바깥 for로 항상 전진, l은 안쪽 while로 필요할 때만 전진 — 둘 다
되돌아오지 않으므로 \(O(N)\)입니다. 이 구현은 모든 값이 양수일 때 단조성이
성립합니다.

2. 정렬된 배열에서 두 수의 합

마주 보는 투 포인터.

sort(a, a + n);                        // 반드시 정렬
int l = 0, r = n - 1;
while (l < r) {
    long long s = a[l] + a[r];
    if (s == target) { /* 찾음 */ break; }
    else if (s < target) l++;          // 합을 키운다
    else r--;                          // 합을 줄인다
}

a.sort()
l, r = 0, n - 1
while l < r:
    s = a[l] + a[r]
    if s == target:
        break
    elif s < target:
        l += 1
    else:
        r -= 1

3. 조건 만족 최장/최단 구간

"합이 \(S\) 이하인 가장 긴 구간"처럼 길이를 최적화하는 변형.

int l = 0, best = 0;
long long sum = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];
    while (sum > S) sum -= a[l++];     // 조건 위반하면 왼쪽 축소
    best = max(best, r - l + 1);       // 유효 구간 길이 갱신
}

"오른쪽으로 늘리고, 조건을 어기면 왼쪽을 줄인다"가 슬라이딩의 일반 골격입니다.

4. 두 정렬 배열 병합 (투 포인터의 또 다른 얼굴)

두 정렬 배열에서 공통 원소 찾기, 병합 등도 투 포인터입니다.

int i = 0, j = 0;
while (i < n && j < m) {
    if (a[i] == b[j]) { /* 공통 */ i++; j++; }
    else if (a[i] < b[j]) i++;
    else j++;
}

5. 흔한 실수

• 단조성 깨짐(음수 포함) — "합이 목표인 구간"에서 음수가 있으면 투 포인터가
  틀립니다(합이 단조롭지 않음). 이땐 누적 합 + 해시맵 등 다른 도구.
• 정렬 빠뜨림 — 마주 보는 투 포인터는 정렬이 전제.
• l이 r을 추월 — while (sum > target && l <= r)처럼 경계를 지키세요.
• 무한 루프 — 두 분기 모두에서 포인터가 반드시 전진하도록.
• 구간 길이 계산 — r - l + 1(닫힌 구간)인지 정확히.

6. 패턴 알아보기

• "연속 부분 배열/구간" + 단조 조건 → 같은 방향 투 포인터.
• "정렬된 배열에서 합/차가 ~인 쌍" → 마주 보는 투 포인터.
• "조건을 만족하는 최장/최단 구간" → 슬라이딩 윈도우 골격.
• \(O(N^2)\)로 보이지만 음수가 없고 단조롭다 → 투 포인터로 \(O(N)\).

실전에서 투 포인터 문제 알아보기

투 포인터의 자격 조건은 단 하나, 단조성입니다. "왼쪽 끝을 오른쪽으로
옮기면 오른쪽 끝도 되돌아갈 필요가 없다"가 성립하는지 묻는 훈련을 합니다.

1. 출제 신호

• 정렬된 배열에서 두 원소의 합/차 조건 — "합이 \(X\)인 쌍의 수". \(O(N^2)\)
  쌍 후보를 양 끝 포인터로 \(O(N)\)에 훑습니다.
• "합이 \(S\) 이상인 가장 짧은 연속 부분 수열" — 원소가 모두 양수면 구간
  합이 단조라 투 포인터가 성립합니다.
• 두 정렬 배열을 동시에 훑기 — 공통 원소, 병합 비교.
• \(N \le 10^5{\sim}10^6\)인데 "연속 구간/쌍"을 묻는다 — \(O(N^2)\) 열거를
  \(O(N)\)으로 줄이라는 신호입니다.
• 판별 질문: "L을 키웠을 때 R이 왼쪽으로 돌아가야 하는 경우가 있는가?"
  없다면 투 포인터, 있다면 다른 도구입니다.

2. 풀이 결정 절차

1. 단조성 확인 — 원소에 음수가 섞이면 구간 합의 단조성이 깨집니다.
   그 경우 투 포인터가 아니라 누적 합 + 해시맵으로 가야 합니다.
2. 무엇을 움직일지 정합니다 — 같은 방향 두 포인터(구간)인가, 양 끝에서
   좁히기(쌍)인가.
3. 이동 규칙을 한 줄로 적습니다 — "조건 만족이면 답 갱신 후 L 증가,
   아니면 R 증가" 식으로.
4. 각 포인터가 최대 \(N\)번만 전진하는지 확인해 \(O(N)\)을 보장합니다.

3. 자주 하는 실수

• 음수 포함 배열에 합 투 포인터. 원소를 추가해도 합이 안 늘 수 있어
  이동 규칙이 무너집니다. 양수 전제를 반드시 확인하세요.
• 양 끝 좁히기에서 두 포인터를 동시에 이동. 합이 목표와 같을 때 한쪽만
  움직이면 같은 값 묶음을 잘못 셉니다. 같은 값이 연속되면 묶음 크기를
  곱해서 세야 합니다.

// 정렬된 a에서 a[l] + a[r] == X인 쌍의 수
int l = 0, r = n - 1; long long cnt = 0;
while (l < r) {
    long long s = (long long)a[l] + a[r];
    if      (s < X) l++;
    else if (s > X) r--;
    else {
        if (a[l] == a[r]) { long long k = r - l + 1; cnt += k * (k - 1) / 2; break; }
        int cl = 1, cr = 1;
        while (a[l + 1] == a[l]) cl++, l++;   // 같은 값 묶음
        while (a[r - 1] == a[r]) cr++, r--;
        cnt += (long long)cl * cr; l++; r--;
    }
}

• 답 갱신 위치. "조건을 만족하는 최소 길이"는 수축하면서 갱신해야
  하고, "만족하는 개수"는 만족 상태에 들어온 순간 세야 합니다. 유형마다
  갱신 지점이 다르니 작은 예제로 검증하세요.
• 합 변수 갱신 누락. 포인터를 옮기며 sum += a[r] / sum -= a[l] 중
  하나를 빠뜨리는 실수 — 창과 합이 따로 놉니다.
• 정렬을 깜빡함. 쌍 문제는 정렬이 전제입니다. 원래 인덱스가 필요하면
  정렬 전에 보관하세요.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순입니다. 정렬
배열의 쌍 문제 → 양수 구간 합 → 조건이 비자명한 변형 순으로 이어집니다.

문제마다 단조성 확인 질문("L을 키우면 R은 한 방향인가?")에 답을 적은 뒤
코딩을 시작하세요. 3문제 이상 풀어 클리어하면 레이팅의 CLASS 보너스에
반영됩니다.