슬라이딩 윈도우
슬라이딩 윈도우은 배열이나 문자열의 연속된 구간을 이동시키며 집계하거나 조건을 검사하는 기법이다 연속 구간 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로...
| 분류 | 알고리즘 · 연속 구간 알고리즘 |
|---|---|
| 목적 | 배열이나 문자열의 연속된 구간을 이동시키며 집계하거나 조건을 검사하는 기법이다 |
| 처리 방식 | 왼쪽과 오른쪽 경계의 이동에 따라 새 원소를 추가하고 제거되는 원소를 집계에서 빼는 방식으로 윈도우 상태를 갱신한다 |
| 복잡도·성능 | 원소가 상수 횟수 들어오고 나가면 O(n), 윈도우 상태 저장 비용은 자료구조에 의존 |
| 필수 조건 | 합계·빈도 등의 집계가 추가·제거 연산으로 효율적으로 갱신되어야 한다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
슬라이딩 윈도우은 배열이나 문자열의 연속된 구간을 이동시키며 집계하거나 조건을 검사하는 기법이다 연속 구간 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 왼쪽과 오른쪽 경계의 이동에 따라 새 원소를 추가하고 제거되는 원소를 집계에서 빼는 방식으로 윈도우 상태를 갱신한다. 고정 길이와 가변 길이 윈도우는 경계 이동 조건이 다르다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 원소가 상수 횟수 들어오고 나가면 O(n), 윈도우 상태 저장 비용은 자료구조에 의존 올바르게 적용하려면 합계·빈도 등의 집계가 추가·제거 연산으로 효율적으로 갱신되어야 한다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 부분 배열 합·중복 없는 부분 문자열·연속 구간 최적화에 사용하며, 단조 큐를 결합하면 이동 구간 최소·최대 질의를 빠르게 계산한다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]