슬라이딩 윈도우(Sliding Window)와 투 포인터(Two Pointer)

선형 탐색에서 시간 복잡도를 비약적으로 줄이는 두 가지 핵심 기법

#️⃣ 들어가며

배열이나 문자열의 연속된 구간에서 특정 조건을 만족하는 부분을 찾을 때 단순 브루트 포스 방식으로 풀 경우 시간 복잡도가 $O(N^{2})$가 되어 시간 초과가 발생한다. 이러한 문제를 선형 시간 $O(N)$에 해결할 수 있도록 도와주는 대표적인 기법이 슬라이딩 윈도우(Sliding Window)와 투 포인터(Two Pointer)이다.

 

---

 

1️⃣ 슬라이딩 윈도우 (Sliding Window)

📌 정의

슬라이딩 윈도우(Sliding Window)는 일정한 크기의 윈도우(구간)을 유지하면서 기존에 구한 결과를 재활용하여 새로운 값을 포함하고, 오래된 값을 제거하며 계산을 빠르게 갱신하는 기법이다. 

슬라이딩 윈도우 기법의 계산 방식

 

🔨 구현 예제

// 배열에서 연속된 구간 k의 원소들의 합 중 최댓값을 찾는 프로그램
int sum = 0, max_sum = 0;

// 초기 값 세팅
for (int i = 0; i < k; i++) 
{
    sum += arr[i];
}

max_sum = sum;

// 윈도우를 오른쪽으로 한 칸씩 이동하면서 갱신
for (int i = k; i < N; i++)
{
    // 윈도우에 새 값을 추가하고, 가장 오래된 값을 제거
    sum += arr[i] - arr[i - k];
    
    max_sum = max(max_sum, sum);
}

 

📚 주요 활용처

• 윈도우(구간)의 크기가 고정되어 있는 경우
• 구간 합, 평균, 최대/최소 등의 값을 반복적으로 계산해야 할 때

 

---

 

2️⃣ 투 포인터 (Tow Pointer)

📌 정의

투 포인터(Two Pointer)는 배열의 인덱스를 가리키는 두 개의 포인터(left, right)를 사용하여 배열을 효율적으로 탐색하는 기법이다. 보통 left는 시작점, right는 끝점을 가리키며 서로 독립적으로 이동하면서 특정 조건을 만족하는 구간을 찾거나 처리한다.

독립적으로 움직이는 두 개의 포인터(left, right)

 

🔨 구현 예제

// 정렬된 양의 정수 배열에서 합이 target인 모든 연속된 부분 수열의 갯수를 구하는 프로그램
int result = 0;
int left = 0, right = 0, sum = 0;

while (right < N) 
{
    // 오른쪽 포인터를 이동시키며 값을 누적
    sum += arr[right++];
    
    // 누적합이 target보다 크면 왼쪽 값을 제거하며 구간을 축소
    while (sum > target)
    {
        sum -= arr[left++];
    }
    
    // 누적합이 정확히 target인 구간이면 결과 카운트 증가
    if (sum == target)
    {
        result++;
    }
}

 

📚 주요 활용처

• 구간의 크기가 일정하지 않아도 상관 없을 때
• 구간의 합, 길이, 조건 만족 여부 등을 반복적으로 확인할 때

 

---

 

3️⃣ 추가 사항

⚡ 모노톤 큐(Monotone Queue)

큐(또는 덱) 안에 항상 정렬된 상태를 유지하도록 원소를 삽입/삭제하면서, 슬라이딩 윈도우 내 최댓값(또는 최솟값)을 $O(1)$ 또는 $O(1) \ amortized$로 조회할 수 있게 해주는 자료구조이다. 각 인덱스는 한 번만 삽입되고, 한 번만 제거되므로 문제를 $O(N)$으로 해결할 수 있으며, 윈도우의 최대/최솟값을 빠르게 유지할 수 있다.

deque<int> dq;

for (int i = 0; i < N; i++)
{
    // 1. 윈도우 범위를 벗어난 값 제거
    if (!dq.empty() && dq.front() <= i - k)
    {
        dq.pop_front();
    }
    
    // 2. 새로 들어올 값보다 작거나 같은 값은 뒤에서 제거
    while (!dq.empty() && arr[dq.back()] < arr[i])
    {
        dq.pop_back();
    }
    
    // 3. 현재 인덱스를 덱에 삽입
    dq.push_back(i);
    
    // 4. 윈도우 크기 도달 시 결과 처리
    if (i >= k - 1)
    {
        result.push_back(arr[dq.front()]);
    }
}

연산	내용
pop_front	윈도우 범위 밖 값 제거
pop_back	새로 들어올 값보다 작은 값 제거
push_back	현재 인덱스를 삽입
dq.front()	현재 윈도우의 최댓값 (or 최솟값) 인덱스

 

✅ 슬라이딩 윈도우와 투 포인터 요약 정리

항목	슬라이딩 윈도우	투 포인터
윈도우 크기	고정된 크기	유동적 (조건에 따라 변동)
포인터 이동 방식	하나 들어오고 하나 나감	조건에 따라 left/right 이동
주요 사용처	고정 구간 최댓값/평균 등	부분 합, 조건 만족 구간

"유동적인 구간"을 탐색할 때는 투 포인터를 사용하고, "고정된 범위"를 빠르게 계산할 때는 슬라이딩 윈도우를 사용한다라고 기억하자.