슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 의미한다. 원래 네트워크에서 사용되던 알고리즘이지만, 문제 풀이에 응용할 수 있다.

슬라이딩 윈도우 기법은 투 포인터 기법과 함께 알고리즘 문제 풀이에 매우 유용하게 사용되는 중요한 기법이다. 투 포인터와 비슷하지만 이와 구분하기 위해 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 따로 구분하기도 한다. 또한 주로 정렬된 배열을 대상으로 하는 투 포인터와 달리 슬라이딩 윈도우는 정렬 여부에 관계 없이 활용된다는 차이가 있다.

투 포인터는 주로 정렬된 배열을 대상으로 한다. [1, 2, 3, 4, 5]가 모두 순서대로 정렬되어 있으며, 처음에는 2개의 포인터가 1과 5를 가리키고 있으나 그 다음에는 왼쪽 포인터만 2를 가리키도록 이동시키거나 2개의 포인터를 모두 움직이는 등의 연산을 통해 탐색해 나간다.

투 포인터는 이처럼 윈도우의 사이즈가 가변적이며, 좌우 포인터가 자유롭게 이동할 수 있는 방식이다. 반면에 슬라이딩 윈도우는 [1, 3, 4, 2, 5]와 같이 정렬되어 있지 않은 배열에도 적용할 수 있다. 윈도우 사이즈는 고정이고, 좌 또는 우 한쪽 방향으로만 이동한다. 실무에서는 때로 혼용되어 쓰이기도 한다.

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

슬라이딩 윈도우는 2개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하는 네트워크 용어이기도 하다. 네트워크에서 패킷을 전송할 때 고정 사이즈의 윈도우가 옆으로 이동하면서 그 다음 패킷들을 전송하는 방식을 말하는데, 지금까지 설명한 슬라이딩 윈도우 알고리즘의 행동 패턴과 동일하기 때문에 슬라이딩 윈도우의 명칭은 여기서 유래한 것으로 추측할 수 있다.

LeetCode 239.Sliding Window Maximum

배열 nums가 주어졌을 때 k 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하면서 최대 슬라이딩 윈도우를 구하라.

Solution 1 브루트 포스로 계산

이 문제는 파이썬의 슬라이싱과 내장 함수를 사용해 매우 쉽게 풀 수 있다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return nums
        r=[]
        for i in range(len(nums)-k+1):
            r.append(max(nums[i:i+k]))
        return r

이 풀이는 문제에서 요구하는 대로 슬라이딩 윈도우를 우측으로 움직여 가며 max()로 최댓값을 추출한다. 매번 윈도우의 최댓값을 계산하기 때문에 시간 복잡도가 O(k*n)이다. 이 풀이는 시간 초과가 발생하였다.

Solution 2 큐를 이용한 최적화

슬라이딩 윈도우를 한 칸씩 움직여야 하는 부분은 개선이 어렵기 때문에 max()를 계산하는 부분에서 최적화를 해야 한다. 정렬되지 않은 슬라이딩 윈도우에서 최댓값을 추출하기 위해서는 어떠한 알고리즘이든 결국 한 번 이상은 봐야 하기 때문에, 최댓값 계산을 O(n) 이네로 줄일 수 있는 방법이 없다. 따라서 가급적 최댓값 계산을 최소화하기 위해 이전의 최댓값을 저장해뒀다가 한칸씩 이동할 때 새 값에 대해서만 더 큰 값인지 확인하고, 최댓값이 윈도우에서 빠지게 되는 경우에만 다시 전체를 계산하는 형태로 개선한다면, 계산량을 획기적으로 줄일 수 있다. 선입선출(FIFO) 형태로 풀이할 수 있기 때문에, 이에 해당하는 대표적인 자료형인 큐를 사용한다. 처음에는 다음과 같이 작성한다.

current_max = float('-inf')
for i, v in enumerate(nums):
	window.append(v)
    if i<k-1:
    	continue
    ...

이 코드에서 k 만큼, 이후 비즈니스 로직은 상관하지 않고 일단 값을 계속 채워 넣는다. 파이썬에서는 큐를 사용하기 위해 deque()를 사용한다.

최댓값이 반영된 상태가 아니라면, 현재 윈도우 전체의 최댓값을 계산해야 한다. 이미 최댓값이 존재한다면 새로 추가된 값이 기존 최댓값보다 더 큰 경우에만 최댓값을 교체한다. 이 부분을 통해 성능 개선할 수 있다. 매번 최댓값을 계산할 필요가 없어지기 때문이다. 이 부분은 다음과 같이 구현할 수 있다.

if current_max == float('-inf'):
	current_max = max(window)
elif v > current_max:
	current_max = v

이처럼 새로 추가된 값이 기존 최댓값보다 더 큰 경우에만, 최댓값을 교체한다. 이 다음에는 최댓값을 결과에 추가한다.

reuslts.append(current_max)

슬라이딩 윈도우는 오른쪽으로 점차 이동한다. 이동하면서 시작하자마자 다시 신규 요소가 추가될 것이므로 가장 오래된 값은 마지막에 제거한다. 이때 만약 그 값이 현재 윈도우의 최댓값이라면, 기존의 최댓값은 더 이상 윈도우에 포함되지 않으므로 다음과 같이 처리한다.

if current_max == window.popleft():
	current_max = float('-inf')

최댓값에 시스템이 지정할 수 있는 가장 낮은 값을 지정하여 초기화하면 이후에 다시 최댓값을 계산하게 할 수 있다. 전체 코드는 다음과 같다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        results = []
        window = collections.deque()
        current_max = float('-inf')
        for i, v in enumerate(nums):
            window.append(v)
            if i < k-1:
                continue
            if current_max == float('-inf'):
                current_max = max(window)
            elif v > current_max:
                current_max = v
            results.append(current_max)
            if current_max == window.popleft():
                current_max = float('-inf')
        return results

필요할 때만 전체의 최댓값을 계산하고 이외에는 새로 추가되는 값이 최대인지만을 확인하는 형태로 계산량을 획기적으로 줄였다. 실행 속도는 이전 풀이에 비해 약 5배 가량 빠르다.