[TIL / Algorithm] 누적합 / Accumulate 함수

조재훈·2024년 8월 13일

TIL algorithm

개요

요즘 재활 운동으로 프로그래머스 기초 PS 문제를 풀다가 다음과 같은 문제를 만났다
n보다 커질 때까지 더하기

사실 기초라서 그냥 반복문을 돌며 푸는 방법으로 해도 되는데 갑자기 이거 보고 예전에 배운 누적합이 생각나면서 누적합으로 풀려 했다가 방법을 까먹어서 어찌어찌 풀었는데 이 참에 제대로 정리해서 넘어가보자

누적합

누적합이란 이름에서 생각할 수 있듯이 수열 An(배열이나 리스트)에 대해서 각 인덱스까지 구간의 합을 배열로 만들어 놓은 것이다
누적합 배열의 첫 번째 원소는 원본 배열의 첫 번째 원소임
모든 구간에 대해 처음부터 계산하여 단순 반복하는 것이 아니라 이전 인덱스까지의 누적합에 현재 자기 자신 값을 더하여 구현하는 것이 효과적인 방법

누적합 배열을 미리 만들어 두면 배열의 [A~B] 구간 합을 구하고자 할 때, 누적합 배열을 구한 후 B까지의 누적합에서 A-1 까지의 누적합을 빼주면 [A~B] 범위의 구간의 합을 구할 수 있다

구현

#include <bits/stdc++.h>

int main()
{
	vector<int> arr = { 15, 98, 23, 2, 15 };

    vector<int> pSum(arr.size());

	pSum[0] = arr[0];

	for (int i = 1; i < arr.size(); i++)
	{
		pSum[i] = pSum[i - 1] + arr[i];
	}

	for (int num : pSum)
	{
		cout << num << " ";
	}
}

누적합 배열을 구할 때는 나는 보통 변수명을 pSum라고 지정한다(prefixSum)

원본 배열의 크기만큼 pSum을 초기화한 뒤 pSum의 첫 번째 원소는 원본 배열의 첫 번째 원소와 똑같이 해주고 반복문을 2번째 원소부터 시작해 누적합을 채워가서 완성한다

누적합 배열을 구하면 원래 반복문으로 구간 합같은 걸 구할 때 이중 반복문을 썼어야 하는데 이건 O(n)으로 가능하다

응용(구간 합 계산)

누적합 배열을 구해 놓으면 원본 배열에서 특정 구간의 합을 바로 구할 수 있다

원본 배열의 [A, B] 합을 구하고 싶을 때는 다음과 같이 하면 된다

pSum[B] - pSum[A - 1]를 하면 된다
A가 0이라면, pSum[B]가 바로 [0, B] 구간의 합이 된다

cout << pSum[3] - pSum[0];

// 123

활용 예시

다수의 구간 합 계산
- 구간 합을 자주 구해야 하는 경우, 매번 O(N)의 시간 복잡도를 갖는 구간 합 계산 대신 누적합 배열을 사용하면 O(1) 시간 복잡도로 구할 수 있다
2차원 배열의 누적합
- 2차원 배열의 구간 합도 누적합 기법을 사용할 수 있다
경쟁 프로그래밍
- 문제에서 구간 합을 반복적으로 구하는 경우, 이 기법을 사용하면 시간 복잡도를 크게 줄일 수 있어 효율적인 문제 해결이 가능함

Accumulate 함수

C++의 표준 라이브러리 함수 중 하나로 배열, 컨테이너의 범위 내 요소들을 합산하거나, 다른 형태(ex. 곱셈)로 누적 계산을 할 때 사용된다. <numeric> 헤더에 정의되어 있음

사용법

기본적으로 accumulate 함수는 두 개의 반복자와 초기값을 인자로 받는다. 첫 번째 반복자부터 두 번째 반복자 바로 앞까지의 모든 요소를 합산해서 그 결과를 반환한다(바로 앞이라는 말 때문에 컨테이너의 end()를 사용할 수 있음)

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};

	// vec의 처음부터 끝까지 더하는데 초기값이 0이다
    int sum = accumulate(vec.begin(), vec.end(), 0);

    cout << "벡터의 합: " << sum;  // 15
}

accumulate 함수의 시그니처는 다음과 같다

T accumulate (InputIterator first, InputIterator last, T init)
T accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op)

first, last, init은 알겠는데 두 번째 줄에 BinaryOperation은 뭘까?

만약 누적 합이 아닌 배열의 모든 요소의 곱을 구하고 싶은 경우에도 이 함수를 쓸 수 있을까? 물론이다. 이때 곱셈을 지정해주기 위해 4번째 인자에 BinaryOperation를 추가해야 한다

가장 쉬운 예시로 배열 내 모든 요소의 곱을 구할 때 주로 쓰는 것이 있는데

int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>());

4번째 인자에 multiplies<int>() 다음을 넣어주면 배열 내 지정한 범위의 곱을 반환한다. 이때 초기값은 1로 해줘야 0이 안되겠지?

아예 커스텀으로 지정하고 싶으면 사용자 정의 함수도 가능하다

int doubleSquare(int a, int b) {
    return a + b * b;  // 예시: 각 요소의 제곱을 더하는 연산
}

int result = accumulate(vec.begin(), vec.end(), 0, custom_operation);