[알고리즘이론] 슬라이딩 윈도우(Sliding Window) 파이썬으로 구현하기

슬라이딩 윈도우(Sliding Window)는 데이터 구조를 이용하여 고정된 크기의 윈도우(Window)를 일정 간격으로 이동시키면서 데이터를 처리하는 기법입니다. 이 기법은 배열, 문자열, 연결 리스트 등 다양한 자료형에 적용할 수 있으며, 주로 연속된 데이터의 부분집합을 찾거나, 부분집합을 이용한 최소 혹은 최대값 등을 찾을 때 사용됩니다.

 

파이썬에서는 리스트나 문자열 등의 자료형에서 슬라이싱(Slicing)을 이용하여 슬라이딩 윈도우를 구현할 수 있습니다. 슬라이싱은 연속된 일정 구간의 원소를 선택할 때 사용하는 파이썬의 기능으로, 다음과 같이 구현됩니다.

 

lst = [1, 2, 3, 4, 5]
window = lst[start:end]  # start 이상 end 미만 구간 선택

 

위 코드에서 start는 선택 구간의 시작 위치, end는 선택 구간의 끝 위치를 나타냅니다. window는 lst 리스트의 start 이상 end 미만 구간에 해당하는 부분 리스트입니다.

 

슬라이딩 윈도우를 이용하여 연속된 부분집합의 합, 최소 혹은 최대값 등을 구하는 문제를 해결할 수 있습니다. 예를 들어, 크기가 k인 슬라이딩 윈도우를 이용하여 리스트 lst의 연속된 부분집합 중 최소값을 찾는 문제를 해결해보겠습니다.

 

lst = [3, 2, 5, 8, 1, 4]
k = 3
min_subarray = []
for i in range(len(lst)-k+1):
    subarray = lst[i:i+k]
    min_val = min(subarray)
    min_subarray.append(min_val)
print(min_subarray)  # 출력: [2, 2, 1, 1]

 

위 코드에서 lst는 입력 리스트이고, k는 슬라이딩 윈도우의 크기입니다. for문에서 리스트 lst에서 크기가 k인 슬라이딩 윈도우를 이동시키면서 최소값을 찾아 min_subarray 리스트에 저장합니다. 이렇게 슬라이딩 윈도우를 이용하여 최소값을 찾는 것은 리스트의 길이에 대한 선형 시간복잡도를 가집니다.