누적합(Prefix Sum)

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

1. 서론

알고리즘 문제를 풀다보면, 종종 배열이 주어지고, 배열 요소의 합을 구하는 문제가 나온다.

예를 들어 크기가 5인 배열에서 3번 index와 5번 index 구간의 구간합을 구하는 문제이다.

이 경우 배열의 크기가 작기 때문에 반복문을 이용해도 충분히 주어진 시간내로 풀 수 있지만, 배열이 길어질 수록 불리해진다.

왜냐하면, 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간 복잡도를 갖기 때문에 입력의 범위가 클때 사용할 수 없기 때문이다.

 

이럴 때 사용할 수 있는 것이 바로 누적합(Prefix Sum)이다.

누적합(Prefix Sum)방식을 사용하면 이러한 문제들을 O(N)으로 해결 할 수 있다.

 

2. 누적합 (Prefix Sum)

서론에서 누적합에 대해 간단히 알아봤으니 이제 누적합을 알아보자.

 

구간 l, r의 합은 다음과 같다.

S[r] - S[l-1]

S는 누적합 배열입니다.

 

누적합이란?

• 요소들이 누적된 합으로, 어떤 배열을 기반으로 요소들의 누적된 합을 저장해 새로 배열을 만들어 이를 활용하는 방법이다.
  • 이때, 기반이되는 배열은 값이 바뀌지 않는 배열이어야 한다.
  • 그래야 구간의 합이 바뀌지 않기 때문이다.
• 앞에서 더하는 prefix sum (주로 코딩테스트에서는 prefix sum만 나온다고 한다.)
• 뒤에서 더하는 suffix sum
• 0번째 요소는 비워두고 1번째 요소부터 사용하는 것이 좋다.
  • S[l - 1] 때문에 시작 index를 0이 아닌 1로 사용해야하는데, 시작 index가 0이었다면, l의 최솟값은 0이고, 이때 l - 1이 -1이기 때문이다. 즉, S[-1]로 접근하게되는 것.
  • 배열의 Index로 음수를 사용할 수 없기 때문에, 1부터 시작하는 것이 좋다.
  • 물론 시작 Index를 0으로 지정해도 누적합을 할 수 있지만, 뒤에 배열 한칸이 더 필요하게 된다.

그림으로 살펴보자.

그림과 같은 배열 A가 있을 때, 누적합 배열 S을 만들어 S에는 해당 Index까지의 합이 기록된다.

이때, 구해야할 구간합 구간 [l, r]이 [3,4] 일때 다음과 같이 구할 수 있다.

실제로 3번 Index ~ 4번 Index까지 더하면 7+ 3이므로 10이 맞다.

 

어떤 문제에서 사용하면 좋은지 예제를 보며 풀어보자.

3. 문제 풀이

예제로 풀어본 문제

2559번: 수열

https://rozentea.tistory.com/52

위의 문제풀이 포스트에는 자새한 설명은 안되어 있으므로 여기서 확인해보자.

위 문제를 for문으로 구현하게 되면, 시간 복잡도가 O(N^2)이고, 주어지는 배열의 범위(각 일간의 온도를 넣은 배열)가 크기 때문에 시간제한으로 문제풀이를 실패하게 된다.

따라서 누적합(시간 복잡도 : O(N))을 이용해 문제를 풀어주어야 한다.

주어지는 온도를 배열로 만든 뒤, 누적합 배열을 만들면 위처럼 vecPS가 나온다.

이때, 주어진 일수(n)안에서 일수(k)간 온도 합이 가장 높은 것을 찾는 문제이다.

누적합 배열을 만든 뒤, 구간합을 이용하면, 제한 시간내로 문제를 풀 수 있다.

vecPS[i] - vecPS[i - k]이고, 시작 Index i를 k로 시작해 i가 n이 될때까지 반복하면,

온도 배열 A안에서 각각 k일수간 온도합을 구할 수 있다.

이후 max()함수를 이용하면, 그 중 가장 높은 온도를 알 수 있다.

 

참고 블로그 및 자료

누적 합

 

C++ 누적합