연속된 k 값들의 합중에서 가장 큰 값을 출력하는 문제의 대표유형
21921번: 블로그
https://www.acmicpc.net/problem/21921
풀이하는 유형은 다양할 것이다. 슬라이싱을 사용할 수도 있고 이중 반복문을 돌릴 수도 있겠다. 하지만 이것은 시간 초과가 날것이다!!! 최적화를 위해 새로운 알고리즘을 탐색하던 중에 슬라이딩 윈도우 를 공부하였다.
투포인터
슬라이딩 윈도우
부분 배열의 크기가 고정적이라는 특징이 있다. 창문을 미는 것처럼! 한 칸씩 옆으로 움직이면서
- 현재의 value를 저장하는 변수
- 한 칸 오른쪽으로 이동하고, 대신 가장 왼쪽의 값을 value에서 빼는 방식
으로 반복문을 배열의 길이만큼만 돌면 된다는 최적화를 이뤄낼 수 있다.
# N, X : 블로그를 시작한 일수, 특정 기간
import sys
N, X = map(int, sys.stdin.readline().rstrip().split())
def max_visitors(arr, day):
global ans, cnt
# 시작과 현재까지 누적합을 할당한다.
start, cur_sum = 0, 0
for end, val in enumerate(arr):
cur_sum += val
if end - start + 1 == day:
if cur_sum > ans :
ans = cur_sum
cnt = 1
elif ans == cur_sum:
cnt += 1
cur_sum -= arr[start]
start += 1
# N일간의 방문자 수가 들어온다.
visitors = list(map(int, sys.stdin.readline().rstrip().split()))
ans = 0
cnt = 0
if sum(visitors) == 0 :
print("SAD")
else:
max_visitors(visitors, X)
print(ans)
print(cnt)
참고한 블로그
[알고리즘][누적합] 슬라이딩 윈도우 알고리즘(Sliding Window Algorithm), 카데인 알고리즘(Kadane`s Algorithm), 원형 배열 부분집합 최대 합 구하기 - 컴도리돌이
오늘 기업 코테를 보았다. 누적합에 대해 2문제씩이나 출제가 되었다. 문제를 다 풀긴 했지만 효율성에서 어떻게 될지 모르겠다. 오늘 코테 풀이에 아쉬움이 남아서 누적합에 대해 다시 돌아보는 시간을 가져보자. 코테의 첫 번째 누적 합의 문제는 연속된 k개의 값들의 합 중에서 가장 큰 값을 출력하는 문제였다. 나는 해당 문제를 슬라이딩 윈도우 알고리즘으로 해결하였다. 슬라이딩 윈도우 알고리즘(Sliding Window Algorihtm)은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다. 예르 들어 정수로 이루어진 배열 {1, 4, 2, 5, 1}에서 길이가 2인 서브 배열의 합계가 가장 큰 서브 배열을 구할 때, 해당 알고리즘을 이용해서 해결한다. 슬라이딩 윈도우는 크기가..
