목차
1. 슬라이딩 윈도우
2. 그림으로 이해
3. 코드
4. 느낀점
슬라이딩 윈도우
슬라이딩 윈도우는 투 포인터 개념과 매우 유사하다.
차이가 있다면 투 포인터는 그 길이가 유동적이지만 슬라이딩 윈도우는 유동적이지 않다는 차이가 있다.
말 그대로 윈도우의 크기를 지정해두고 그 윈도우 자체를 슬라이딩 한다는 개념이다.
투 포인터를 안다면 바로 그림으로 이해해보자.
투 포인터를 모른다면 3장에서 설명했으니 참고하면 좋겠다.
3장 투 포인터 : 링크텍스트
그림으로 이해
아래와 같은 리스트가 존재한다.
윈도우의 길이는 3이라고 하고, 윈도우에 들어있는 합이 가장 큰 경우를 찾아야 한다고 가정하자.
(윈도우는 리스트에서 연속된 수로 이어진다.)
윈도우를 시각화하면 아래와 같다.
이 때 윈도우 안에 있는 수들의 합 = num[0] + num[1] + num[2] 이다.
(num은 리스트 변수 이름이다.)
이제 윈도우를 오른쪽 방향으로 옮겨야한다.
옮기는 과정을 시각화해보면 아래와 같다.
기존 윈도우의 가장 왼쪽에 있던 부분은 빠지고 가장 오른쪽 변에 인접해 있는 리스트의 원소가 더해진다.
이 과정을 거칠 때 윈도우 안에 있는 수들의 합 = window - num[0] + num[3]이다.
이 과정을 계속 반복하다보면 이 상태에서 끝나게 된다.
중간에 기존의 MAX보다 크다면 초기화한다.
여기서는 MAX = 5 + 7 + 4 = 16이 정답이다.
코드
num = [1, 2, 1, 5, 7, 4, 3]
list_len = len(num) # 리스트의 길이
n = 3 # 윈도우의 길이
window = 0
for i in range(n):
window += num[i]
MAX = window # 처음 최댓값
start = 0 # 처음 윈도우에서 뺄 인덱스
end = n # 처음 윈도우에서 더할 인덱스
while end < list_len:
window -= num[start]
window += num[end]
start += 1
end += 1
if window > MAX:
MAX = window
print(MAX)느낀점
나는 처음 슬라이딩 윈도우를 배울 때 투 포인터의 개념을 완전히 이해하지 못한 상태로 들어갔었다.
하지만 현재 투 포인터 개념을 어느정도 학습하고 난 뒤 슬라이딩 윈도우 개념을 이해하려고 노력하니 훨씬 더 쉽게 이해가 되는 기회가 되었다.
투 포인터 개념을 학습하면 자동으로 슬라이딩 윈도우 개념이 따라오는 것 같았다.
