투 포인터 & 슬라이딩 윈도우

1. 투 포인터(Two Pointers)란?

정렬된 배열이나 리스트에서 두 개의 인덱스를 사용해 탐색 범위를 조절하는 기법

• 목적: 모든 경우를 다 보지 않고(완전탐색), 필요 없는 탐색을 건너뛰어 시간 절약
• 기본 구조: left와 right 두 개의 인덱스를 조건에 맞게 이동시키며 범위 탐색

핵심 아이디어

1. 정렬 필요: 대부분 정렬된 상태에서 사용 (정렬 O(n log n))
2. 포인터 이동은 단조롭게 → 뒤로 돌아가지 않음 (O(n) 탐색)
3. 합/곱/조건을 만족하면 결과를 저장하고 범위를 조절

2. 투 포인터 기본 패턴

(1) 양 끝에서 시작

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) {
        // 정답 처리
    }
    if (sum > target) right--;
    else left++;
}

예시: 두 용액(백준 2470), 수 고르기(백준 2230)

(2) 같은 방향으로 이동

int left = 0, right = 0;
while (right < n) {
    if (조건 만족) {
        // 갱신
        right++;
    } else {
        left++;
    }
}

예시: 연속된 수들의 합, 부분합(백준 1806)

3. 슬라이딩 윈도우(Sliding Window)란?

연속된 구간(subarray)의 합, 평균, 최대/최소 등을 빠르게 계산하기 위해 윈도우(구간)를 유지하며 한 칸씩 밀어서 이동하는 기법

• 목적: 구간합/구간조건 계산을 O(1)로 줄이기
• 차이점: 투 포인터는 조건 맞출 때 포인터 간 거리 가변적, 슬라이딩 윈도우는 윈도우 크기가 고정(또는 제한적으로 변동)

고정 크기 윈도우

int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i]; // 첫 구간 합

for (int i = k; i < n; i++) {
    sum += arr[i] - arr[i - k]; // 새 값 더하고, 이전 값 빼기
}

예시: 최대 연속 합(백준 2559), 평균이 가장 높은 구간

가변 크기 윈도우 (투 포인터와 겹침)

int left = 0, sum = 0, answer = 0;
for (int right = 0; right < n; right++) {
    sum += arr[right];
    while (sum > target) {
        sum -= arr[left++];
    }
    answer = Math.max(answer, right - left + 1);
}

예시: 부분합 문제(백준 1806), 조건 만족하는 가장 긴 구간 찾기

4. 시간 복잡도

• 투 포인터 / 슬라이딩 윈도우 모두 O(n)
• 정렬이 필요한 경우: O(n log n)
• 윈도우 내 계산은 O(1)

5. 코테에서의 구분 팁

구분	특징	예시 문제
투 포인터	두 인덱스가 독립적으로 움직이며 범위 조정	두 용액, 수 고르기
슬라이딩 윈도우	한쪽 끝이 따라가며 연속 구간 유지	최대 연속합, 평균 계산
가변 윈도우	조건 만족하는 연속 구간	부분합, 문자열 포함 여부

6. 실전 팁

1. 투 포인터 문제 = 정렬 + O(n) 패턴이 많음
2. 구간합 문제 = 슬라이딩 윈도우로 O(n)로 줄이는 게 핵심
3. 문자열 문제에도 응용 가능 (아나그램, 특정 문자 포함 여부)
4. 투 포인터와 슬라이딩 윈도우는 사실상 "같은 틀의 변형"