슬라이딩 윈도우(백준 알고리즘 12847번)

♠ 슬라이딩 윈도우   

윈도우(특정 범위)가 있을 때 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘. 고정된 범위를 탐색할 때 유용하며 중복으로 연산을 제거하면서 효율을 높일 수 있다. 한 칸씩 이동하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다. 투 포인터와 비슷하지만, 슬라이딩 윈도우는 고정된 범위를 탐색하는 것이기 때문에 두 개의 포인터가 없어도 된다.  

 

위의 배열에서 연속적인 4개 숫자의 합이 최대인 값을 구한다고 가정한다. 

[1, 3, 2, 6] => 합: 12

[3, 2, 6, -1] => 합: 10

[2, 6, -1, 4] => 합: 11

[6, -1, 4, 1] => 합: 10 

 

이렇게 계산을 하면 중복되는 부분이 생긴다. 중복을 줄이기 위해 처음과 끝 원소만 갱신하는 코드를 구성한다. 

arr=list(map(int,input().split()))

total = sum(arr[:4])

for i in range(4, len(arr)-4+1): 
    total+=arr[i] 
    sum-=arr[i-4]   
    print(sum)

 

 

♠ 백준 알고리즘 12847번

 

 

주어진 날은 5개인데, 연속되는 3개 요소의 합 중 가장 큰 값을 출력하는 것이다. 슬라이딩 윈도우를 이용하여 아래와 같이 코드를 작성할 수 있다. 

 

♠ 참고 자료

https://learning-e.tistory.com/36

[Algorithm] 슬라이딩 윈도우(Sliding Window) 알고리즘 with python

 

https://velog.io/@nana-moon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-window-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0Two-pointer

[알고리즘] 슬라이딩 윈도우(Sliding window), 투 포인터(Two pointer)