Technical Interview Master Plan [4] - Sliding Window를 알아도 왜 부분 배열 문제에서 자꾸 막히는가

Sliding Window 기법에 대해 개념과 문제 해결 전략에 대해 배워봅니다.

Introduction to Sliding Windows

슬라이딩 윈도우 기법은 투 포인터(two-pointer) 패턴의 하위 개념으로, 배열과 같은 반복 가능한(iterable) 자료구조에서 두 개의 포인터(일반적으로 left와 right)를 사용하여 “윈도우”의 경계를 정의합니다.

이 윈도우는 데이터 구조의 하위 구성 요소(예: 부분 배열이나 부분 문자열)를 정의하며, 데이터 구조를 한 방향으로 이동하면서 특정 조건을 만족하는 하위 구성 요소를 탐색하는 기법입니다.

슬라이딩 윈도우는 그렇지 않으면 모든 가능한 하위 구성 요소를 찾기 위해 두 개의 중첩 반복문(two nested loops)을 사용해야 하는 상황에서 특히 유용합니다. 이는 O(n²) 시간 복잡도, 또는 그 이상이 될 수 있습니다.

반면 Sliding Windows 슬라이딩 윈도우를 사용하면, 우리가 찾고자 하는 하위 구성 요소를 보통 O(n) 시간 안에 찾을 수 있습니다. 이제 동작 방식을 설명하기 전에 몇 가지 용어를 정리해보도록 하겠습니다.