Readiz
검색
← 강의
기록

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

포인터를 되돌리지 않아도 되는 이유를 살피고, 음수 반례로 적용 범위를 확인합니다.

#알고리즘#C++#기본기Markdown으로 읽기
이 글의 목차
  1. 언제 필요한가
  2. 정렬된 배열에서 양끝 포인터
  3. 조건을 만족하는 가장 짧은 구간
  4. 조건을 만족하는 가장 긴 구간
  5. 로컬 연습: 목표 합 이상인 가장 짧은 구간
  6. 예시
  7. 직접 움직이며 전제 확인하기
  8. 완성 파일로 실행하기

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

언제 필요한가

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

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

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

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

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

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

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

코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

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 이상 구간을 찾습니다. 합이 부족하면 오른쪽을 늘리고 충분하면 왼쪽을 줄입니다.

그림 크게 보기

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

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 같은 다른 도구가 필요할 수 있습니다.

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

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

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입니다.

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

예시

6 7
2 3 1 2 4 3
2

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

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

슬라이딩 윈도우와 음수 반례 실험

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

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

완성 파일로 실행하기

C++17 전체 예제 내려받기

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

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

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

이전 사이트에서 옮긴 글입니다. 원래 주소