[C++] 누적 합을 함수 한 방에 구하여보자! partial_sum

종종 누적 합(partial_sum) 알고리즘을 사용하기 위하여 각 부분별 부분 합을 구할 때가 많다. 그럴 때 우리는 이런식으로 코드를 작성하였다.

 

vector<int> nums의 처음부터 끝까지 각 부분별 누적합을 구하고, 이를 vector<int> acc_nums에 담는다고 가정하자.

 

vector<int> nums, acc_nums;
acc_nums[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
    acc_nums[i] = acc_nums[i-1] + nums[i];
}

 

위와 같은 코드를 단 두 줄의 코드로 압축할 수 있으면 믿을 것인가? 누적 합을 쉽게 위하여 C++에는 partial_sum이라는 함수가 정의되어 있다.

 

1. partial_sum

(※ https://www.cplusplus.com/reference/numeric/partial_sum/ 에서 함수에 대한 정보를 확인할 수 있다.)

 

C의 Sequence 관련 여러 함수들이 담긴 헤더 <numeric.h>에서의 partial_sum 함수는 다음과 같이 두 가지 구조를 가진다.

 

 1] sum - OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result)

2] custom - OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op)

 

partial_sum은 쓰임에 따라 3개 혹은 4개의 인자를 받는다.

 

 

• ForwardIterator first : 배열이나 어떤 container 자료형의 시작부 혹은 포인터
• ForwardIterator last : 배열이나 어떤 container 자료형의 끝부 혹은 포인터
• OutputIterator result: 결과를 담을 배열이나 어떤 container 자료형의 시작부 혹은 포인터

 

만약, partial_sum이 누적 합이 아닌, 다른 방식으로 배열이나 어떤 container의 값들을 더하고 싶다면 마지막에 하나의 인자를 추가한다.

 

 

• BinaryOperation binary_op : 첫 번째 인자로 여태까지 누적된 것들의 합, 두 번째 인자로 배열이나 어떤 container의 값을 받는 함수. 이 함수는 원래의 값을 수정하여서는 안되고, 인자로 넘길 때 함수 객체나 포인터로 넘길 수 있다.

 

네 번째 인자가 조금 어려울 수 있지만, C++의 accumulate 함수와 같은 방법으로 동작하기에 예시를 보면서 이해해보자.

 

구체적으로 이 함수의 역할을 말하자면, 범위 [first, last)에서 4번째 인자가 없다면 1~1번째 구간, 1~2번째 구간, $\cdots$, 1~N번째 구간까지의 누적 합을 구하여 result가 가리키는 iterator에 하나씩 결과를 담고, 4번째 인자가 존재한다면 custom으로 누적된 결과를 담는다. 같은 역할을 하는 코드를 작성하면 다음과 같이 작성할 수 있다.

 

// 1. sum
template <class InputIterator, class OutputIterator>
   OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result) {
 
  if (first!=last) {
    typename iterator_traits<InputIterator>::value_type val = *first;
    *result = val;
 
    while (++first!=last) {
      val = val + *first; // sum
      *++result = val;
    }
    ++result;
  }
 
  return result;
}
 
// 2. custom
template <class InputIterator, class OutputIterator>
   OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result) {
 
  if (first!=last) {
    typename iterator_traits<InputIterator>::value_type val = *first;
    *result = val;
 
    while (++first!=last) {
      val = binary_op(val,*first); // custom partial summing
      *++result = val;
    }
    ++result;
  }
 
  return result;
}

 

 

쉽게 말해, first 부터 last까지 더하거나 직접 설정한 방법으로 값들을 쌓으면서 결과를 result에 담는 함수라 생각하면 된다.

 

잘 모르겠으면 다음과 같은 식으로 표현할 수 있다. 누적 합을 구하고 싶은 본래 배열이나 container의 원소들을 각각 $x_0,\,x_1,\,\cdots,\,x_n$이라 하고, $y$는 누적 합의 결과라 나타내면, 각 $y$는 다음과 같이 계산할 수 있다.

 

$$ \begin{align*}
y_0 &= x_0\\
y_1 &= x_0 + x_1\\ 
y_2 &= x_0 + x_1 + x_2\\
&\vdots\\
y_n &= x_0 + x_1 + \cdots + x_n
\end{align*} $$

 

2. 예제 코드

먼저, partial_sum - (1) sum을 활용하는 예시를 들어보자.

 

맨 처음의 코드는 다음과 같이 바꿀 수 있다.

 

vector<int> nums, acc_nums;
partial_sum(nums.begin(), nums.end(), acc_nums.begin());

 

매우 간단하게 vector 정의와 partial_sum을 이용하여 간단히 누적 합의 중간 결과들을 result에 담을 수 있다. 만약 누적 합의 결과만 필요하다면 accumulate 함수를 사용하면 된다.

---

다음으로, partial_sum - (2) custom을 사용할 때를 알아보자.

 

만약, 각 수들을 더하는 대신, 각 수들을 빼고 싶을 땐 어떻게 할까? 이때 4번째 인자로 각각 어떻게 누적할 지 넣어주면 된다.

 

2-1) Using lambda function

람다 함수를 사용하여 임시로 필요한 함수를 생성한다면 값을 더하는 대신 뺄 수 있다.

 

위의 예시에서 람다 함수를 이용하여 만약 각 값에 대한 뺄셈을 차례차례 수행할 것이다.

 

#include <iostream> // cout
#include <numeric> // partial_sum
#include <vector> // vector
using namespace std;
 
int main() {
 
    vector<int> nums = {1, 2, 3};
    vector<int> acc_nums(3, 0);
    partial_sum(nums.begin(), nums.end(), acc_nums.begin(), 
                [](int x, int y) { return x - y; }
    );
 
    for (auto i: acc_nums) { cout << i << ' ';}
    // cout : "1, -1, -4"
 
    return 0;
}
 

 

실제 코드를 실행하여보면 누적으로 뺄셈을 진행하며 acc_nums에 {1, -1, -4}가 담기는 것을 확인할 수 있다. 

 

2-2) Using function call overloading

함수 호출 연산자 오버로딩이나 따로 함수 객체를 사용하여 partial_sum의 네 번째 인자를 채울 수 있다. 같은 역할을 수행하므로 람다 함수를 이용할때와 같은 결과를 얻을 수 있다.

 

#include <iostream> // cout
#include <numeric> // partial_sum
#include <vector> // vector
using namespace std;
 
struct myclass {
    int operator()(int x, int y) { return x-y; }
} myobj;
 
int main() {
 
    vector<int> nums = {1, 2, 3};
    vector<int> acc_nums(3, 0);
    partial_sum(nums.begin(), nums.end(), acc_nums.begin(), myobj);
 
    for (auto i: acc_nums) { cout << i << ' ';}
    // cout : "1, -1, -4"
 
    return 0;
}

 

혹은 C++에서 여러 연산 정보를 담고 있는 헤더 <functional.h>에서 정의되어있는 연산을 활용할 수 있다. 

헤더에 정의되어 있는 std::minus<int>를 사용하여 코드를 작성하면 위와 같은 결과를 얻을 수 있다.

 

#include <iostream> // cout
#include <numeric> // partial_sum
#include <vector> // vector
#include <functional> // minus
using namespace std;
int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> acc_nums(3, 0);
 
    partial_sum(nums.begin(), nums.end(), acc_nums.begin(), minus<int>());
 
    for (auto i: acc_nums) { cout << i << ' ';}
    // cout : "1, -1, -4"
    
    return 0;
}

 

이외에도 다른 연산을 활용하거나 직접 자신만의 누적합 결과를 쌓아나갈 수 있다.

 

3. 주의할 점

1.

partial_sum 함수는 기본적으로 누적 합을 구하는 연산이기에, 언제나, 언제나, 언제나 각 자료형에 대한 ※overflow※ 를 반드시 염두에 두어야 한다.

 

만약, partial_sum 연산의 결과가 overflow가 발생할 것을 미리 알고 있다면, 적절한 자료형으로 type casting 해주거나 미리 초깃값을 0 대신 0LL 을 사용하는 등 조치를 취하여 오버플로우를 방지할 수 있다.

 

2.

partial_sum의 내부에서는 iterator를 이용하여 값을 채우기 때문에, 결과를 담을 배열이나 container에 미리 공간이 할당되어야 한다. 만약 공간이 미리 할당되어 있지 않다면, undefined behavior가 발생하거나 결과가 저장되지 않을 수 있다.

 

partial_sum 함수도 하나씩 배열에 접근하기에 시간 복잡도는 배열의 길이인 $O(n)$을 가지며, 만약 배열의 범위를 초과하여 index에 접근할 경우 undefined behavior가 발생할 수 있다. 만약, custom 방법을 사용한다면, $O(nK)$ ($K$는 custom 연산의 시간 복잡도)라고 쓸 수 있다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!