99클럽 코테스터디 5일차 TIL - 백준 2559

문제: https://www.acmicpc.net/problem/2559

해당 문제는 슬라이딩 윈도우 개념을 활용하여 풀 수 있는 문제이다.

슬라이딩 윈도우는 배열에서 하나의 틀(부분 배열)을 일정한 크기 만큼 이동시키며 문제를 풀이하는 알고리즘이다.

문제의 예제 2를 참고하여 원리를 보면 다음 그림과 같다.

 

위와 같이 배열 안에서 분홍색의 고정된 크기만큼 이동하며 각 경우의 합을 세게 되는데, 한칸씩 이동할때마다 이전의 값을 삭제하되 이후의 값을 더하는 방식으로 시간복잡도를 줄이는 방식이다.

 

이 문제는 "연속적인 며칠 동안의 온도의 합이 가장 큰 값" 을 확인하는 문제이고, "연속적인"에서 고정된 크기 내의 원소들의 합을 구해야한다는 점과 배열의 원소 갯수인 N이 최대가 100,000 이하(=10^5)라는 점에서 보통처럼 for문 중첩 등을 통해 해결할 수 없어 시간복잡도를 줄이면서 연속합을 구해야하는 점에서 슬라이딩 윈도우 알고리즘 사용을 떠올릴 수 있었다.

 

 

✅ 풀이

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
arr = list(map(int, input().split()))
sliding_window = sum(arr[:k])
answer = sliding_window

for i in range(n-k):
  sliding_window -= arr[i]
  sliding_window += arr[i+k]
  answer = max(answer, sliding_window)

print(answer)

 

오늘의 배운점

- 배열에서 "일정한 크기"의 연속합을 구하거나 혹은 일정크기를 움직여가며 특정 작업을 수행할때, 슬라이딩 윈도우를 활용하자