---
id: "lessons/two-pointers-sliding-window"
title: "투 포인터와 슬라이딩 윈도우: 창을 움직이는 조건"
description: "포인터를 되돌리지 않아도 되는 이유를 살피고, 음수 반례로 적용 범위를 확인합니다."
kind: "record"
published: "2026-10-04T00:00:00.000Z"
tags: ["알고리즘","C++","기본기"]
url: "https://www.readiz.com/records/two-pointers-sliding-window/"
markdownUrl: "https://www.readiz.com/records/two-pointers-sliding-window/index.md"
---

# 투 포인터와 슬라이딩 윈도우: 창을 움직이는 조건

투 포인터는 배열이나 문자열에서 두 위치를 움직이며 필요한 구간이나 쌍을 찾는 방법입니다. 모든 쌍을 `O(n^2)`으로 보지 않고, 포인터가 한 방향으로만 움직이게 만들어 `O(n)` 또는 `O(n log n)`으로 줄이는 것이 핵심입니다.

## 언제 필요한가

아래 신호가 보이면 투 포인터를 먼저 의심합니다.

- 정렬된 배열에서 합이 특정 값이 되는 두 수를 찾는다.
- 연속 구간의 합, 길이, 종류 수를 묻는다.
- 오른쪽 끝을 늘리면 조건이 좋아지거나 나빠지는 방향이 일정하다.
- 같은 원소를 여러 번 세지 않으면서 모든 후보 구간을 훑어야 한다.

핵심은 **한 포인터가 되돌아가지 않아도 되는가**입니다. 왼쪽 포인터와 오른쪽 포인터가 각각 최대 `n`번만 움직이고 이동당 갱신이 `O(1)`이면 전체 시간은 `O(n)`입니다.

## 정렬된 배열에서 양끝 포인터

정렬된 배열에서 두 수의 합을 확인할 때는 왼쪽 끝과 오른쪽 끝에서 시작합니다.

```text
a[l] + a[r] < target 이면 l을 오른쪽으로 이동
a[l] + a[r] > target 이면 r을 왼쪽으로 이동
```

정렬되어 있기 때문에 `l`을 오른쪽으로 옮기면 합은 커지고, `r`을 왼쪽으로 옮기면 합은 작아집니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
bool hasPairWithSum(vector<int> a, int target) {
    sort(a.begin(), a.end());
    int l = 0;
    int r = (int)a.size() - 1;
    while (l < r) {
        long long sum = (long long)a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) l++;
        else r--;
    }
    return false;
}
```

## 조건을 만족하는 가장 짧은 구간

![양수 배열2,1,3,2에서 합5 이상 구간을 찾습니다. 합이 부족하면 오른쪽을 늘리고 충분하면 왼쪽을 줄입니다.](https://www.readiz.com/assets/lessons/array-ranges/window-trace.svg)

[그림 크게 보기](https://www.readiz.com/assets/lessons/array-ranges/window-trace.svg)

모든 값이 양수라면 오른쪽 끝을 늘릴수록 구간 합은 커지고, 왼쪽 끝을 줄일수록 구간 합은 작아집니다. 이 단조성 덕분에 합이 `target` 이상인 가장 짧은 연속 구간을 `O(n)`에 찾을 수 있습니다.

```cpp
int minLengthAtLeastSum(const vector<int>& a, long long target) {
    int n = (int)a.size();
    int answer = n + 1;
    int left = 0;
    long long sum = 0;

    for (int right = 0; right < n; right++) {
        sum += a[right];
        while (left <= right && sum >= target) {
            answer = min(answer, right - left + 1);
            sum -= a[left];
            left++;
        }
    }

    return answer == n + 1 ? -1 : answer;
}
```

값에 음수가 섞이면 오른쪽을 늘렸을 때 합이 항상 커지지 않습니다. 그때는 누적합 + 자료구조, prefix minimum, deque 같은 다른 도구가 필요할 수 있습니다.

## 조건을 만족하는 가장 긴 구간

구간 안의 서로 다른 값 개수, 최대 빈도, 합의 상한처럼 "오른쪽을 늘리면 조건이 깨질 수 있고, 왼쪽을 줄이면 회복된다"는 형태도 자주 나옵니다.

```cpp
int longestAtMostKDistinct(const vector<int>& a, int k) {
    if (k <= 0) return 0;
    unordered_map<int, int> freq;
    int left = 0;
    int answer = 0;

    for (int right = 0; right < (int)a.size(); right++) {
        freq[a[right]]++;
        while ((int)freq.size() > k) {
            int value = a[left++];
            if (--freq[value] == 0) freq.erase(value);
        }
        answer = max(answer, right - left + 1);
    }

    return answer;
}
```

해시 테이블 연산이 평균 `O(1)`이라는 전제에서 전체 평균 시간은 `O(n)`입니다.

`while` 조건에는 "현재 창이 유효하지 않은 동안"을 넣습니다. 유효해진 뒤에 답을 갱신하면 창이 항상 문제 조건을 만족합니다.

## 로컬 연습: 목표 합 이상인 가장 짧은 구간

양수 배열에서 합이 S 이상인 연속 구간의 최소 길이를 구하세요. 그런 구간이 없으면 0입니다.

**입력:** N S와 길이 N의 배열. 1 <= N <= 200000, 1 <= a\[i] <= 1000000, 1 <= S <= 10^12입니다.

**출력:** 최소 길이 하나를 출력합니다.

### 예시

```text exercise=two-pointers-sliding-window role=input
6 7
2 3 1 2 4 3
```

```text exercise=two-pointers-sliding-window role=output
2
```

**확인 방법:** 마지막 \[4,3]의 길이가 2입니다. N <= 30에서 모든 구간을 열거해 비교합니다. 한 원소가 바로 S 이상인 경우와 전체 합이 S보다 작은 경우를 검사합니다. 음수 입력으로 바꾼 경우에는 창의 단조성이 유지되지 않습니다.

## 직접 움직이며 전제 확인하기

[슬라이딩 윈도우와 음수 반례 실험](https://www.readiz.com/learn/explore/?demo=window)

기본 예제에서는 `[2, 3, 1, 2, 4, 3]`과 목표 합 7을 사용합니다. 오른쪽 값을 더하고, 합이 충분한 동안 현재 길이를 기록한 뒤 왼쪽 값을 뺍니다. 각 단계에서 실제 구간, 합, 지금까지 찾은 최소 길이를 함께 표시합니다.

‘음수 반례’를 고르면 `[1, -1, 5]`, 목표 5로 같은 코드를 실행합니다. 전체 길이 3을 기록한 뒤 1을 빼면 합이 4가 되어 축소를 멈춥니다. 하지만 그다음 -1도 빼면 `[5]`만 남으므로 실제 답은 1입니다. **이 데모의 결과 3은 의도적으로 드러낸 오답**이며, 양수 입력용 함수를 음수 입력에 적용하면 안 되는 이유입니다. 목표는 항상 양수입니다.

## 완성 파일로 실행하기

[C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/array-ranges/two-pointers-sliding-window.cpp)

표준 헤더와 본문의 세 함수, 로컬 연습용 `main`을 포함합니다. 위 예시를 `input.txt`에 저장해 실행하면 2가 나옵니다.

```sh
c++ -std=c++17 -O2 two-pointers-sliding-window.cpp -o window-demo
./window-demo < input.txt
```

`minLengthAtLeastSum` 함수는 답이 없으면 -1을 반환합니다. 연습 문제의 출력 약속은 0이므로 `main`이 -1을 0으로 바꿉니다. 실행 파일은 양수만 입력받으며, 음수 반례는 웹 데모에서 별도로 확인합니다.