누적합, 슬라이딩 윈도우

\

누적합

핵심 아이디어 : 배열의 각 인덱스까지의 합을 미리 계산하여 별도의 배열에 저장해 둔다.

목적 : 특정 구간 [i, j]의 합을 매우 빠르게 (O(1)) 계산하기 위함.

A[i] 부터 A[j]까지의 합은 P[j] - P[i-1]로 구할 수 있다.

N개의 원소로 이루어진 수열, 이 중 연속하는 K개의 원소들의 합 중 가장 큰 값

• 연속하는? -> 누적합 구해놓으면 빼는것만으로 연속하는 원소들 합 구하기 가능 -> O(1) ,

• 대략N번 돌면서 구하면 되니까(원소들 개수) -> O(N)에 해결 가능

슬라이딩 윈도우

• 핵심 아이디어: 고정된 크기 k의 '창문(window)'을 배열 위에서 한 칸씩 움직여가며, 창문 안의 데이터를 처리합니다.

  • 목적: 고정된 크기 k를 갖는 모든 연속된 부분 배열에 대해 특정 계산(예: 최대/최소 합, 평균 등)을 효율적으로 수행하기 위함입니다.

  • 동작 방식:

    1. 처음 k개 요소로 첫 윈도우를 구성하고 값을 계산합니다.

    2. 윈도우를 한 칸 오른쪽으로 이동시킬 때, 새로 들어오는 요소는 더하고, 맨 왼쪽에서 나가는 요소는 뺍니다.

    3. 매번 윈도우 전체를 다시 계산하는 것이 아니라, O(1)의 연산으로 윈도우의 값을 갱신합니다.

  • 장점: 전체 배열을 한 번만 순회(O(N))하므로, 고정 크기 k의 모든 부분 배열을 탐색하는 데 매우 효율적입니다.

  • 단점: 윈도우의 크기가 고정되어 있거나, 특정 조건에 따라 유동적으로 변하는 문제에 특화되어 있습니다.

• 배열과 배열의 부분배열의 원소들을 어떠한 조건 하에 계산하는 상황에서 사용된다.

• ex) 구간 합 구하기, 일정한 사이즈의 범위 값 계산하기 , 가장 긴 부분 문자열 구하기

사이즈가 k로 고장되어있음 전에 이용했던 크기 합을 이용해서 O(N)만에 최대합을 구할 수 있음.

만약 누적합으로 이걸 구하면 누적합 계산하는데 O(N) , 누적합 배열 탐색하는데 O(N) -> O(N^2)임

사실상 걍 O(N* K) 돌아서 탐색하는거