[알고리즘] 투포인터 vs 슬라이딩 윈도우

투 포인터, 슬라이딩 윈도우 이 두 가지는 코딩테스트에서 자주 출제되는 핵심 패턴이지만 헷갈리기 쉽다.

둘 다 배열이나 문자열에서 연속된 구간을 다룰 때 주로 사용한다.

 

결론부터 말하자면

투포인터는 구간을 "늘렸다 줄였다" 하며 조건에 만족하는 것을 찾는다.
슬라이딩 윈도우는 구간의 크기를 "고정하고 민다"

투포인터 (Two Pointer)란?

투포인터는 말 그대로 포인터 2개를 사용하는 방법이다.
left, right 두 개의 포인터로 구간을 조절한다.

 

핵심은

조건에 따라서 늘리거나(right++) 줄이거나(left++) 조절을 통해 조건을 만족하는 지 확인한다.

투포인터를 언제 쓰냐?

• 연속 부분합이 어떤 조건을 만족하는지 찾기
• 정렬된 배열에서 두 수의 합 찾기
• 특정 조건을 만족하는 가장 짧은/가장 긴 구간 찾기

투포인터 코드 틀

합이 target 이상인 최소 길이를 구하는 자바 코드

int left = 0;
int sum = 0;
int answer = Integer.MAX_VALUE;

for (int right = 0; right < n; right++) {
    sum += arr[right];

    while (sum >= target) {
        answer = Math.min(answer, right - left + 1);
        sum -= arr[left];
        left++;
    }
}

---

슬라이딩 윈도우란?

슬라이딩 윈도우는 말 그대로 창문(window) 하나를 배열 위에서 미는 느낌이다.
크기가 고정된 구간을 오른쪽으로 이동 (항상 길이 k 유지)

 

핵심은

길이가 고정된 구간을 한 칸씩 옮긴다.

 

슬라이딩 윈도우를 언제쓰냐?

• 길이 k인 연속 부분배열의 최대 합
• 문자열에서 길이 k인 부분 문자열 처리
• “연속된 k개” 문제

슬라이딩 윈도우는 빠지는 값 하나를 빼고 새로 들어오는 값 하나를 더해서 O(1)로 갱신하는 게 핵심이다.

 

슬라이딩 윈도우 코드 틀

int sum = 0;

// 초기 윈도우
for (int i = 0; i < k; i++) {
    sum += arr[i];
}

int answer = sum;

// 윈도우 이동
for (int i = k; i < n; i++) {
    sum -= arr[i - k]; // 빠지는 값
    sum += arr[i];     // 새로 들어오는 값
    answer = Math.max(answer, sum);
}

 

---

투포인터와 슬라이딩 윈도우 비교

구분	투포인터	슬라이딩 윈도우
구간 크기	변함	고정
목적	조건 만족 찾기	구간 값 계산
이동 방식	확장/축소	한 칸씩 이동

 

투포인터

• 구간 길이 변함
• 조건 만족할 때까지 늘리거나 줄임
• “최소 길이”, “최대 길이”, “조건 만족 구간” 문제

슬라이딩 윈도우

• 구간 길이 고정
• 한 칸씩 밀면서 갱신
• “연속된 k개” 문제