C++: 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)

• 투포인터와 유사한 개념이지만, 두 원소의 관계를 보기보단 구간을 판단하는 목적으로 2개의 포인터를 사용할 때 슬라이딩 윈도우라고 말한다.
  • ex)배열속 연속된 5숫자 합의 최대, 동일하지 않은 문자로 이루어진 가장 긴 부분문자열 등
• 새로 모두 계산해 값을 찾아내기보단, 기존의 값에서 갱신만 해나가며 빠르게 처리해나간다.
• 돌아오지 않고 한쪽으로만 움직이며 처리하기에 단조성에 의해서 $O(n^2)$이 아닌 $O(n)$으로 처리한다.
• 사용조건
  • 연속된 부분 구간을 판단하는 문제
  • n개 혹은 최소/최개 길이로 부분문자열의 크기에 대해 조건이 정해진 문제
  • 합, 평균같은 갱신으로 누적 가능한 형태

고정크기 vs 가변크기

• 윈도우의 범위는 고정적일수도, 가변적일 수도 있으며, 이는 문제에 따라 다르다.
  • 앞서 말한 연속된 5숫자의 합에서 최대를 찾는다면 윈도우의 간격이 고정되어 있다.
    • 때문에 앞뒤 양쪽의 포인터를 동시에 움직이며 간격을 맞춘다.
  • 앞서 말한 가장 긴 부분문자열을 찾는 문제라면 간격이 고정되어 있지 않다.
    • 한쪽 포인터를 고정한 후 다른 포인터만 움직이다가 조건에 어긋나면 고정했던 포인터를 움직인다.

자료구조와의 결합

• 상황에 따라 다른 자료구조와 결합하여 사용할 수 있다.

상황	자료구조	갱신시 복잡도
합,평균,갯수	int 변수 한개	$O(1)$
중복 확인	셋	평균 $O(1)$
빈도 확인	맵	평균 $O(1)$
빈도	벡터/리스트	$O(1)$

활용

• 게임
  • 최근 fps
  • 최근 데미지
  • 최근 점수합
  • 매프레임 합산/평균내야할 것을 효율적으로 처리
• 웹서버
  • 요청 제한
  • 최근 횟수
  • 최근 에러율
  • Apache Kafka/Spark - 빅데이터 실시간 파이프라인
  • Redis, Prometheus 내부에서도 사용!
• CS 전반
  • 빅테이터 스트림 처리
  • TCP/IP 흐름 제어
    • 보낼 수 있는 데이터의 양이 곧 윈도우
    • ACK(확인 패킷)을 받을때마다 한칸 이동
    • 이름도 같은 방식으로 제어
  • 디지털 신호 처리(Digital Signal Processing, DSP)
  • 시계열 분석(Time Series Analysis)
  • 끝없는 데이터의 처리
• 계산 대신 갱신으로 처리 가능한 실시간 시스템 전반에 응용