Coding Test(Sliding Window)

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이요해 문제를 풀이하는 알고리즘

● Brute Force - list slicing 을 이용한 방법

for i in range(len(nums)-k+1):
    r.append(max(nums[i:i+k]))

●  queue을 이용한 방법 (Fast)

for i, v in enumerate(nums):
	window.append(v)
    if i<k-1:
    	continue

 

하지만 이러한 경우는 k 크기 만큼의 윈도우를 리스트에서 계속 탐색 해야하기 때문에 O(k * n)의 시간복잡도를 가진다.

 

 

 

 

● 슬라이딩 윈도우 활용 (구간합, 누적합, Prefix sum)

이렇게 되면 전체 시간 복잡도는 O(N)이 되며 시간복잡도를 많이 줄일 수 있다.

 

투 포인터는 정렬된 상태에서 써야 하지만 슬라이딩 윈도우는 제약을 받지 않고 일정한 윈도우 크기로 움직인다