[til] 알고리즘 백준 수열

📘 TIL (Today I Learned)

🧑‍💻 오늘의 문제: 2559번 수열

📌 문제 요약

• 연속적인 K일 동안의 온도 합이 가장 큰 값을 찾는 문제이다.

• 주어진 온도의 수열에서 연속된 K개의 합을 구하고, 그 중 최대값을 출력하면 된다.

🚩 알고리즘 분류

• 누적 합 (Prefix Sum)

• 슬라이딩 윈도우 (Sliding Window)

---

🖥️ 내가 작성한 코드 (슬라이딩 윈도우 방식 사용)

import sys

n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

# 초기 K개 합 계산
current_sum = sum(arr[:k])
max_sum = current_sum

# 슬라이딩 윈도우 방식으로 합을 갱신하며 최대값을 찾는다.
for i in range(k, n):
    current_sum += arr[i] - arr[i - k]
    max_sum = max(max_sum, current_sum)

print(max_sum)

🔎 풀이 핵심 아이디어

• 첫 번째 K개의 숫자를 합해서 초기 합계를 구한다.

• 이후, 슬라이딩 윈도우 기법을 이용하여 한 칸씩 오른쪽으로 이동하면서,
  이전에 더한 가장 왼쪽 값을 빼고, 새로 더할 가장 오른쪽 값을 더해 합을 갱신한다.

• 갱신한 합을 매번 비교하며 최대 합을 구한다.

---

🔍 추가로 찾아본 좋은 풀이 방법 (다른 사람 풀이 참고)

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

# 누적합(prefix sum)을 미리 계산하여 활용
prefix_sum = [0]
for num in arr:
    prefix_sum.append(prefix_sum[-1] + num)

max_sum = -float('inf')
for i in range(k, n + 1):
    max_sum = max(max_sum, prefix_sum[i] - prefix_sum[i - k])

print(max_sum)

💡 위 풀이에서 배운 점

• 누적 합(Prefix Sum)을 미리 구해놓으면, 부분합을 매우 빠르게 구할 수 있다.

• 슬라이딩 윈도우가 직관적이고 빠르지만, 누적 합도 다양한 부분합을 빠르게 구하는 데 유용하다.

• Prefix Sum을 계산할 때 0을 시작점으로 넣어두면, 인덱스 계산이 쉬워져 깔끔하게 구현이 가능하다.