[C++] 아직도 sum += arr[i] 쓰시나요? accumulate으로 해결하세요!

accumulate 함수는 많은 C++ 사용자들에게 널리 알려져 있지만, 그래도 아직 모르는 사용자들이 있다고 생각되어 포스팅을 남긴다.

 

std::accumulate 함수는 특정 배열 혹은 container의 누적 합을 구할 때 사용가능한 함수이다. 특히, 전체 합을 구하거나, 한 번의 누적 합을 구할 때 사용할 수 있다.

 

함수 accumulate를 사용하지 않고 누적 합을 구한다면 다음과 같이 작성할 수 있다. 예를 들어, vector<int> nums 안에 있는 모든 원소들의 합을 구한다고 가정하여보자. 다음과 같이 코드를 작성할 수 있다.

 

int sum = 0;
for (int i = 0; i < (int)nums.size(); i++) {
    sum += nums[i];
}

 

코드 자체는 길지 않지만, accumulate는 누적 합을 구하는 것 이외의 응용을 할 수 있는 방법이 무궁무진하다.

 

1. accumulate

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

 

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

 

 1] sum - T accumulate (InputIterator first, InputIterator last, T init)

2] custom - T accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op)

 

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

• ForwardIterator first : 배열이나 어떤 container 자료형의 시작부 혹은 포인터
• ForwardIterator last : 배열이나 어떤 container 자료형의 끝부 혹은 포인터
• T init: 하나씩 더할 값의 초깃값

 

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

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

 

네 번째 인자가 조금 어려울 수 있는데, 이는 예시를 보며 이해하면 빠르게 이해할 수 있다.

 

구체적으로 이 함수의 역할을 말하자면, 범위 [first, last) 에서 4번째 인자가 없다면 누적 합을 반환하고, 4번째 인자가 존재한다면 custom으로 누적된 합을 반환한다. 같은 역할을 하는 코드를 작성하면 다음과 같이 작성할 수 있다.

 

// 1. sum
template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init) {
  while (first!=last) {
    init = init + *first; // sum
    ++first;
  }
  return init;
}
 
// 2. custom
template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init) {
  while (first!=last) {
    init = binary_op(init,*first) // custom accumulation
    ++first;
  }
  return init;
}

 

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

 

2. 예제 코드

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

 

위의 예시와 같이 nums 안의 모든 코드의 합을 구한다고 할 때 다음과 같이 작성할 수 있다.

 

int sum = accumulate(nums.begin(), nums.end(), 0);

 

매우 간단하게 한 줄로 끝낼 수 있지 않은가? 만약 특정 구간의 합을 구하고 싶다면 첫 번째 인자로 시작 iterator, 두 번재 인자로 끝 iterator, 세 번째 인자로 초깃값을 넘겨주면 된다.

 

만약 누적 합에 대한 중간 계산 결과를 별도의 배열이나 container에 담고싶다면 별도의 함수를 사용해야 한다. (partial_sum)

---

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

 

만약, 각 수들을 더하는 대신, 각 수들을 빼주고 싶을 땐 어떻게 할까? 이를 세 가지 방법으로 구현하여보자.

 

2-1) Using lambda function

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

 

예를 들어, vector<int> = {1, 2, 3}이 있다면, 아래의 코드는 값을 각 값에 대하여 뺄셈을 수행할 것이다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    vector<int> nums = {1, 2, 3};
    // 0 - 1 - 2 - 3
    int sum = accumulate(nums.begin(), nums.end(), 0, [](int x, int y) { return x - y; });
    
    cout << sum;
    // cout : -6
}

 

실제 코드를 실행하여보면 -6 이라는 값이 나온다는 것을 확인할 수 있다. 어떻게 실행되는 지 모르겠다면, 위의 구체적으로 풀어 쓴 코드에서 init = binary_op(init, *first) 가 어떤 방식으로 수행될 지 생각해보면 된다.

 

2-2) Using function call overloading

struct나 class에서의 함수 호출 연산자 오버로딩을 통해 연산을 수행할 수 있다. 위의 방법처럼 뺄셈을 하고 싶다면 다음과 같이 함수 객체를 이용하여 코드를 작성할 수 있다. 같은 역할을 수행하므로 같은 결과인 -6 을 반환한다.

 

#include <bits/stdc++.h>
using namespace std;
 
struct myclass {
    int operator()(int x, int y) { return x - y;}
} myobject;
 
int main() {
    vector<int> nums = {1, 2, 3};
    // 0 - 1 - 2 - 3
    int sum = accumulate(nums.begin(), nums.end(), 0, myobject);
    
    cout << sum;
    // cout : -6
}

 

이처럼, 함수 객체를 활용하여 accumulate의 누적 합을 custom 할 수 있다.

 

2-3) Using <functional.h>

C++에서 여러 연산 정보를 담고 있는 헤더 <functional.h>에는 어떻게 연산해야할지에 관한 정보를 담고 있다. 2-2) 와 비슷한 방법이지만, 바퀴가 만들어져 있는데 굳이 새로운 바퀴를 만들 필요는 없지 않은가?

 

위의 예시에서 헤더 <functional.h>에 정의되어 있는 std::minus<int>를 활용한다면 같은 연산 결과를 얻을 것이다.

 

#include <iostream> // cout
#include <numeric> // accumulate
#include <vector> // vector
#include <functional> // minus
 
using namespace std;
 
int main() {
    vector<int> nums = {1, 2, 3};
    // 0 - 1 - 2 - 3
    int sum = accumulate(nums.begin(), nums.end(), 0, minus<int>());
    
    cout << sum;
    // cout : -6
}

 

혹은 헤더에 정의되어 있는 std::multiplies를 이용하면 각 원소간 곱도 손쉬운 방법으로 구현할 수 있다.

 

#include <iostream> // cout
#include <numeric> // accumulate
#include <vector> // vector
#include <functional> // multiplies
 
using namespace std;
 
int main() {
    vector<int> nums = {1, 2, 3};
    // 1 * 1 * 2 * 3
    int sum = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
    
    cout << sum;
    // cout : 6
}

 

다만, 위 예시에서의 다른 예시와 다른 점은 multiplies를 활용할 때는 초깃값이 1이어야 제대로 된 누적곱을 구할 수 있다.

 

3. 주의할 점

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

 

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

 

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

 

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

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