[알고리즘] 슬라이딩 윈도우

슬라이딩 윈도우란?

• 배열/문자열 위에 window를 올려놓고, 오른쪽으로 밀면서 탐색하는 기법이다.
• 완전탐색 $O(N²$) → $O(N)$ 으로 줄이는 게 핵심이다.

빈출 유형

• 연속된 구간에서 최대/최소/개수를 구할 때 등장한다

1) 고정 크기 윈도우

예) "크기 K인 연속 부분 배열의 최대 합"

• 창문 크기 K가 고정되어 있다.
• right가 움직이면 left도 같이 움직인다.

2) 가변 크기 윈도우

예) "합이 S 이하인 가장 긴 연속 부분 배열", 개미 집합의 지름 문제

• 조건에 따라 창문 크기가 늘었다 줄었다한다.
• left/right 독립적으로 움직인다.

3) 반대 방향 투 포인터

예) "두 수의 합이 target인 쌍 찾기", "3Sum"

• 정렬 후 left/right를 양 끝에서 좁혀오는 방식이다.
• 투 포인터가 슬라이딩 윈도우를 포함하는 더 큰 범위이다.

적용 가능한지 판단하는 기준

기준	설명
① 연속된 구간인가?	인덱스가 연속되어야 한다. 부분집합/순열이면 X
② 단조성이 있는가?	right 늘릴수록 값이 커지기만 해야 한다. 음수 포함 시 주의
③ left 복원 가능한가?	left 당기면 조건이 다시 만족되어야 한다.

하나라도 X면 슬라이딩 윈도우 적용이 어렵다

기록

• 개미 집합의 지름
  • 처음 접근: 투포인터 그리디 (X)
    • 개미 집합의 지름 문제를 풀면서, 투포인터로 접근했다.
    • 매 순간 왼쪽/오른쪽 중 제거 시 더 많이 줄어드는 쪽을 제거하는 방식을 채택했다.
      → 그리디는 현재 최선만 보기 때문에 전체 최적을 보장하지 않음!!!!
      • 반례) 1 3 4 10, D=2
        그리디: 3번 제거 / 최적: 2번 제거 (1, 10 제거)
• 올바른 접근: 슬라이딩 윈도우 (O