슬라이딩 윈도우란?
슬라이딩 윈도우는 투포인터와 비슷하면서도 다른 알고리즘입니다.
2개의 포인터로 범위를 지정한 다음, 범위를 유지하면서 이동(Sliding)합니다.
그리고 해당 범위 내의 원소가 주어진 조건을 만족하는지 검사하는 알고리즘 기법입니다.
슬라이딩 윈도우의 사용법을 그림을 통해서 간단하게 표현하면 위와 같습니다.
주어진 범위인 4(데이터 창)를 그대로 유지하면서 start와 end의 인덱스를 함께 플러스하여 순차적으로 데이터를 탐색합니다.
이러한 슬라이딩 윈도우는 네트워크 트래픽의 분석, 스트리밍 데이터 처리 등에 사용되기도 합니다.
코드 구현
주어진 문제는 N개의 수로 이루어진 수열 중에서,
K개의 연속되는 숫자로 구성되는 부분수열 중 합이 가장 최대가 되는 값을 구하는 문제입니다.
K개라는 범위로 데이터 창을 만들어서 N개의 원소를 담은 배열을 순회하면서 값을 비교함으로써 답을 도출할 수 있습니다.
해답 코드입니다.
초기 부분 수열인 0 ~ K-1까지의 수를 모두 더하여 curSum에 초기화합니다.
이후 K ~ N-1까지의 원소를 반복문으로 탐색하면서, 부분수열의 최댓값을 구합니다.
값의 갱신은 arr[i] - arr[i+K]로 이루어집니다.
이는 이전 start 인덱스에 해당하는 값을 제거하는 코드입니다.
이를 그림으로 표현하면 다음과 같습니다.
현재 End 인덱스에 저장된 값에 데이터 창의 범위인 K를 빼면 바로 이전 start 인덱스를 구할 수 있고 curSum에서 해당 값을 제외하면 새로운 범위의 값을 구할 수 있는 것입니다.
이를 배열의 범위인 N-1까지 반복하면서
curSum을 maxSum과 비교함으로써 정답을 구할 수 있습니다.
이러한 슬라이딩 윈도우는 고정 메모리를 사용하기 때문에 상수의 메모리를 사용함으로써 자원의 할당 및 해제 등의 관리가 편하고 공간복잡도의 예측면에서 용이하다는 장점이 있습니다.
