1주차 개념 #9. 누적합(prefix sum)

1주차 개념 #9. 누적합(prefix sum)

자 오늘은 누적합이라는걸 배워보도록 할게요.

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다.

오늘은 prefix sum 이라는 걸 배워보도록 할거에요.

뭐냐면 예를 들어서 배열이 1, 10, 11, 100 이라는 요소의 배열이 있다라고 칩시다. 이따가 코드 보면서 설명을 드릴건데, 누적합을 만들 때는 원본 배열 자체를 0번째는 아무런 값을 담지 않고 첫번째, 두번째, 세번째, 네번째 이런 식으로 담아야 돼요.

그러니까 보통 배열을 만들 때는 0번째부터 시작한다고 하잖아요. 그런데 prefix sum을 만들 때는 1번째부터 배열을 담아놔야 돼요.

이제 prefix sum 이라고 하지 않고 우리는 psum 이라고 부를거에요.

이 psum 이라는 배열의 첫번째 요소는 첫번째까지 합한거, 두번째는 첫번째와 두번째까지의 원소를 합한거,

이렇게 {1, 10, 11, 100} 이러한 배열을 기반으로 새로운 배열을 만드는데, 첫번째 요소는 첫번째 것까지, 두번째 요소는 첫번째 것과 두번째 것을 더한 거로 만드는 거예요.

그리고 이렇게 만든 배열을 기반으로 어떤 연산에 활용할 수가 있다라는 거죠.

근데 참고로 이제 이런 prefix sum 말고 suffix sum 이라는 것도 존재해요.

suffix sum은 뭐냐면 뒤에서부터 이렇게 더하는 거거든요. 코딩 테스트에는 prefix sum만 나와요. 알고리즘 대회를 나간다면 suffix sum도 알아두셔야 합니다.

---

자 그러면 이걸 어디다 쓸까?

예를 들면서, 문제를 보면서 설명을 해보도록 할게요.

자 문제를 읽어보시면 단순해요. A부터 B까지의 어떤 합을 구하라는 거예요. 근데 이 A부터 B까지의 이 구간은 달라질 수가 있는 거죠.

예제 입력을 기반으로 제가 한번 그림을 만들어 볼게요.

이런 식으로 출력이 나와야하는데, 이걸 프로그램으로 만들어야 돼요.

아주 단순하게 이제 구현을 하면은 이렇게 되겠죠.

이렇게 해서 출력을 하면 되겠거니 라는 생각이 들 거예요. 근데 여러분 제가 항상 문제를 볼 때 "최대, 최소 범위를 생각하라" 라고 말씀을 드렸죠.

자 그러면 이 문제의 최대 범위를 잠깐 볼까요?

N과 M은 둘 다 10만이죠. 그럼 만약에 N과 M 둘 다 최악의 경우인 10만이라면 이 코드의 시간 복잡도는 얼마일까요?

일단 이게 10만번 반복이 되죠?

그리고 이 것도 N의 최대 범위가 10만이기 때문에 10만번 반복이 되네요.

이렇게 코드를 짜게 되면은 여러분들이 짠 코드는 10만 곱하기 10만이라는 시간복잡도를 가지게 돼요. 100억인 거죠. 당연히 100억짜리 시간 복잡도는 잘 안됩니다.

그럼 다른 알고리즘을 생각을 하셔야 되는데, 자 그러면 어떻게 될까?

이때 나온 게 바로 누적합입니다. 이러한 큰 시간 복잡도를 줄일 수 있는 하나의 방법이 prefix sum, 누적합이라는 거예요.

지금 이 문제는 구간쿼리 문제입니다.

구간쿼리란 뭐냐면,

말 그대로 이런식으로 구간을 정해서 구간에 대한 합이나 곱이나 마이너스 등의 연산을 하는 구간에 대한 쿼리를 날리는 것을 말하는데, 이거는 구간합쿼리 라고 할 수 있어요. 구간에 대한 합을 구하라는 요청인거죠.

자 그러면 우리가 앞서서 배운 psum을 어떻게 활용할 거냐면은 psum이라는 개념이 뭐였죠?

제가 한번 그대로 psum을 통해서 한번 해볼게요.

psum을 만들면 이런 식으로 되겠죠. 만약에 선생님이 2부터 5까지의 합을 구하라 라고 했어요.

그럼 이 구간의 합은 psum[5] - psum[1]이겠네요.

그럼 만약에 선생님이 2부터 3까지의 합을 구하라고 하면,

psum[3] - psum[1]이겠네요.

미리 이렇게 앞에서부터 누적을 해놓은 합인 psum을 기반으로 하니까,

우리가 앞서서 본 이런 코드처럼 일일이 구간쿼리가 왔을 때마다 더할 필요가 없겠죠.

그냥 단순하게 마이너스 연산만으로 가능하네요.

따라서 구간쿼리 라고 했을 때 두 가지 생각이 나셔야 돼요. 하나는 우리가 지금 설명한 prefix sum이고, 나머지 하나는 나중에 배울 펜윅 트리가 생각이 나셔야 돼요.

psum 같은 경우는 배열의 요소가 정적 배열이에요. 지금 배열의 요소들이 중간에 변하나요? 문제를 다시 보면,

문제에서 이 {1, 2, 3, 4, 5, 6, 7, 8} 이라는 배열의 요소들이 변하지 않죠. 이걸 정적 배열이라고 하는 거예요.

근데 만약에 문제에서 이 배열 요소가 어느 순간 순간마다 2는 100으로, 4는 50으로 변해요. 이런 동적 배열 같은 경우는 누적합을 쓸 수가 없어요. 동적 배열은 펜윅 트리를 써야돼요.

근데 이 문제 같은 경우는 배열의 요소가 변하지 않기 때문에 정적 배열이라서, psum을 써서 해결할 수가 있는 거죠. 일단은 이런 배열의 구간 쿼리에 대해서는 누적합을 쓸 수 있다는 것만 알아둡시다.

그리고 배열의 요소가 변하지 않는, 정적 배열인 경우에만 누적합을 활용할 수 있다 라고만 알아두시면 됩니다.

아무튼 이런식으로 우리가 앞서서 설명한 이 코드처럼 매번 더하는게 아니라, psum을 쓰면 마이너스만 있죠.

자 마이너스는 뭐라고 했죠? O(1)의 상수시간의 시간 복잡도를 가진다고 했죠.

그렇기 때문에 시간복잡도를 10만 곱하기 10만이 아니라, 10만 곱하기 1로 줄일 수 있다라는 겁니다.

자 그러면 이 psum을 만드는 코드는 어떻게 될까요?

이렇게 됩니다. 코드를 잠깐 보겠습니다.

이 부분을 잠깐 볼까요?

우리가 psum이 뭔지는 파악을 했어요. 앞에서부터 누적해서 합을 만드는 거죠. 물론 만들 때마다 다 더해서 만들 수도 있지만 그렇게 하면은 조금 그렇습니다.

그럼 어떻게 해서 만드느냐? 만들어 놓은 psum[1]이 있을 거 아니에요. psum[2]는 미리 만들어 놓은 psum[1]에다가 a[2]를 더한 거잖아요.

그 이전의 psum 에다가 지금의 배열에 요소를 더한다는 거죠.

그리고 나서, 쿼리를 처리할 때는 이런식으로 마이너스만 해주시면 되는 거구요.

지금 psum을 만들 때, i - 1이 들어가잖아요. 그렇기 때문에 i는 1부터 해야된다고요. 만약에 i를 0부터 하게 되면 이게 마이너스 1이 돼가지고 배열 자체를 참조할 수가 없잖아요.

그래서 배열은 0부터 시작하니까 psum을 조금 더 쉽게 만들려고 1부터 받아야 된다라고 말씀을 드린 거예요.

 

다시 누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열(psum)을 만들어서 이를 활용하는 것을 말합니다.

그럼 어떠한 부분에서 활용이 되냐?

이런 식으로 구간쿼리인데,

이런 식으로 배열의 요소들이 변하지 않는, 정적 배열에서 활용된다.

그리고 i = 1부터 해서 psum[i - 1] + a[i]로 psum[i]를 만든다. 여기까지 알아봤습니다.