[Algorithm][Python] 슬라이딩 윈도우(Sliding Window)

📕1. 슬라이딩 윈도우 알고리즘이란?

• 투포인터와 유사한 알고리즘 ( 투포인터와 달리 '일정한 크기' )

• 슬라이딩 윈도우는 정렬되지 않아도 사용 가능함. 좌우 모두 움직이는 '투포인터'와 달리 슬라이딩 윈도우는 좌우 중 한 방향으로만 이동함.

• 배열 또는 리스트와 같은 순차적 데이터 구조에서 일정한 크기의 "윈도우"를 움직여가며 특정 연산을 수행하는 기법.

• 주어진 배열에서 연속된 서브 배열의 합, 최댓값, 최솟값 또는 특정 조건을 만족하는 부분 배열 등을 찾는 경우에 슬라이딩 윈도우 알고리즘이 유용하게 적용될 수 있음.

• 슬라이딩 윈도우 알고리즘은 반복문을 통해 한 번만 배열을 탐색하므로 시간 복잡도는 O(n)이므로 전체 배열을 다시 계산하는 것보다 효율적인 시간 복잡도를 가짐.

 

📕2. 알고리즘 동작 원리 설명

• [2, 5, 3, 6, 7, 1] 이라는 예시 리스트가 있다고 가정하자.

• 연속된 3개의 요소를 합했을 때, 가장 큰 값을 구해보면서 슬라이딩 알고리즘을 이해해 보자.

• 연속된 3개이기 때문에, 윈도우의 크기는 3.

 

2

5

3

6

7

1

• 최댓값은 리스트의 0번째,1번째,2번째 요소들의 합과 같이 때문에 2+5+3 = 11

 

2 (-)

5

3

6 (+)

7

1

• 다음으로는 윈도우를 한 칸 이동해 보자.

  이전 윈도우와 비교했을 때 5와 3이 겹치는 숫자이므로 이 숫자는 재사용하면 된다.

  그러므로 이전 윈도우에서 구한 11이란 값에서 2를 빼고 6만 더해주면 된다.

  이번 윈도우에서 구한 값은 14이므로 최댓값 갱신.

 

2

5(-)

3

6

7 (+)

1

• 마찬가지로 윈도우를 한 칸 옮긴 후, 이전 구한 값 14에서 5를 빼고 7을 더하면 됨.

  16이므로 최댓값 갱신.

 

2

5

3(-)

6

7

1 (+)

• 이전 구한 값 16에서 3을 빼고 1을 더함. 최댓값이 아니므로 갱신 X

  슬라이딩 윈도우에서 이전 값을 빼고 새로운 값을 더하는 과정은 O(1)의 시간 복잡도를 가진다.

  그리고 결과적으로 이 알고리즘에서 가장 큰 구간합은 16이 된다. 

 

 

 

📕3. Python 코드 

# 슬라이딩 윈도우 파이썬 코드
lst = [2,5,3,6,7,1]
n = len(lst)
k = 3 # 윈도우의 크기 (고정적인 숫자)

res = lst[0] + lst[1] + lst[2] # 같은 표현 : res = sum(lst[:k])

for i in range(1,n-2):
   res = max(res, res - lst[i-1] + lst[i+2])  #O(1)

print(res)

 

📕4.  백준 2559 - 수열

 

문제 1) 백준 2559. 수열

2559번: 수열

4-1 ) 실패코드

# 실패코드
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
temp = list(map(int,input().split()))

maxx = 0
for i in range(N-K+1) :
    summ = sum(temp[i:i+K])
    if summ > maxx :
        maxx = summ
print(maxx)

5개월 전의 슬라이딩 윈도우를 모르던 내가 풀었던 코드. 당연히 시간초과가 났음.

4-2 ) 정답코드

N,K = map(int,input().split())
lst = list(map(int,input().split()))

res = sum(lst[:K])
ans = res
for i in range(N-K) :
    res += lst[i+K] - lst[i]
    ans = max(ans,res)

print(ans)