[백준/Python] 2559 수열

[백준/Python] 2559 수열

정답 코드 및 설명

전체 코드

# 입력 받기
N, K = map(int, input().split()) # N은 전체 날짜의 수, K는 연속적인 날짜의 수
temperatures = list(map(int, input().split())) # 매일의 온도

# 슬라이딩 윈도우 초기화
current_sum = sum(temperatures[:K]) # 처음 K일 동안의 온도 합
max_sum = current_sum

# 슬라이딩 윈도우를 이용한 최대 온도 합 계산
for i in range(K, N):
    current_sum += temperatures[i] - temperatures[i-K]
    max_sum = max(max_sum, current_sum)

# 최대 온도 합 출력
print(max_sum)

문제 설명

위 수열 문제는 일정 기간 동안 매일 측정된 온도가 정수의 수열로 주어진다. 목표는 연속적인 며칠 동안의 온도의 합이 최대가 되는 값을 찾는 것이다. 즉, 주어진 수열에서 특정 길이 K 의 연속된 부분 수열의 합 중 최댓값을 찾아야 한다.

위 문제를 효율적으로 풀기 위한 방법 중 하나는 '슬라이딩 윈도우' 기법을 사용하는 것이다. 슬라이딩 윈도우 기법은 배열이나 리스트의 일정 범위의 데이터를 연속적으로 처리해야할 때 사용하는 알고리즘 기법이다. 이 기법의 핵심은 윈도우 라고 할 수 있는 고정된 크기의 범위를 가지고 이 범위를 배열이나 리스트를 따라 한 칸 씩 이동하면서 필요한 계산을 수행하는 것이다.

코드 설명

1. 먼저 k개의 요소로 구성된 윈도우 합을 계산한다. 이를 current_sum 으로 한다 이는 0~k 의 원소 합이다.

2. 윈도우를 한 칸 씩 오른쪽으로 이동하면서 새로 윈도우에 들어오 는 요소를 current_sum 에 더하고 윈도우에서 빠져나가는 요소를 current_sum 에서 뺴준다. 이렇게 하여 갱신된 current_sum 이 이전의 max_sum 보다 크면 max_sum 을 바꿔준다

3. 모든 위치에서 슬라이딩이 끝나면 계산된 최대 합 max_sum 을 출력한다.