[파이썬 알고리즘 인터뷰] 슬라이딩 윈도우

• 슬라이딩 윈도우: 고정 사이즈의 윈도우가 이동하며 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘
  • 정렬 여부와 관계없이 사용
  • 좌 또는 우 한 방향으로만 이동
  • 교과서에 정의된 내용이 아니며, 투 포인터와 혼용하여 쓰기도 하고, 원래 네트워크에서 사용되던 알고리즘

이름	정렬 여부	윈도우 사이즈	이동
투 포인터	대부분 O	가변	좌우 포인터 양방향
슬라이딩 윈도우	X	고정	좌 또는 우 단방향

 

239. Sliding Window Maximum

- 브루트 포스

- 큐로 최적화 -> 윈도우 이동하여 최댓값 계산 시, 이전 윈도우의 최댓값이 빠질 때만 새로 계산

 

※ 고정된 윈도우 크기로 탐색하면서 필요한 계산 수행 (가능하면 계산 최소화하여 구현)

 

76. Minimum Window Substring

- 브루트 포스

- 슬라이딩 윈도우가 우측으로 이동하다 적절한 위치에서 좌측 포인터 좁혀나가는 투 포인터 방식

- Counter()의 AND 연산 이용 -> 무거운 & 연산의 반복으로 매우 느림

 

424. Longest Repeating Character Replacement

- right가 끝까지 이동하면서 최대크기 윈도우가 성립하지 않을때만 left도 한칸만 이동 (최대 크기 값은 자동으로 저장)

 

※ right로 반복 탐색함과 동시에 Counter()로 각 데이터의 빈도를 실시간으로 저장하며 조건부로 left 이동하는 구조