42-4.수치 알고리즘

42-4-가.accumulate

수치 관련 알고리즘들은 STL에 직접적으로 소속되지 않으며 C++ 라이브러리로 분류된다. 그러나 수치 알고리즘도 STL 컨테이너와 함께 훌륭하게 동작하며 STL이 C++ 표준 라이브러리에 흡수된 이상 이를 굳이 구분할 필요는 없다. 단, 이 함수들은 numeric 헤더 파일에 정의되어 있으므로 수치 관련 함수를 쓸 때는 이 헤더 파일을 꼭 포함하도록 하자. 누적 합을 구하는 함수는 다음 두 가지이다.

 

T accumulate(InIt first, InIt last, T val [, BinOp op]);

OutIt partial_sum (InIt first, InIt last, OutIt result [ ,BinOp op]);

 

accumulate 함수는 first ~ last 구간에 속한 값들의 총합을 구한다. 세 번째 인수 val은 누적 총합의 초기값인데 0으로 지정하면 순수한 합을 구할 수 있다. partial_sum은 first ~ last까지의 부분합들을 구해 result 반복자 위치에 순서대로 대입한다.

 

: accumulate

#include <iostream>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

 

template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";

      copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

 

void main()

{

     int ar1[]={49,26,19,77,34,52,84,34,92,69};

     vector<int> vi1(&ar1[0],&ar1[10]);

     printf("벡터의 총합은 %d이다.\n",accumulate(vi1.begin(),vi1.end(),0));

 

     int ar2[]={1,2,3,4,5,6,7,8,9,10};

     vector<int> vi2(&ar2[0],&ar2[10]);

     vector<int> vi3;

     partial_sum(vi2.begin(),vi2.end(),back_inserter(vi3));

     dump("부분합",vi3);

}

 

정수 10개가 들어 있는 벡터의 총합을 accumulate 함수로 구했다. 그리고 1 ~ 10까지의 정수가 들어 있는 벡터의 부분합을 vi3 벡터에 새로 작성했다.

 

벡터의 총합은 536이다.

부분합      ==> 1 3 6 10 15 21 28 36 45 55

 

총합은 모든 요소값을 더한 것이므로 쉽게 이해가 될 것이다. 부분합이란 first에서부터 반복자까지의 합을 더한 값의 벡터인데 1까지 더하면 1, 1과 2를 더하면 3, 1과 2와 3을 더하면 6, 이런 식으로 앞 요소들의 값을 계속 더해 나가면서 중간 중간의 결과값을 벡터로 다시 작성한다. 일종의 누적값에 대한 벡터를 만드는데 예를 들어 sale 벡터에 월별 판매량이 있다면 이 벡터에 대한 누적합들은 해당월까지의 총 판매량이 된다.

accumulate 함수는 반복자 구간을 순회하면서 이 값들을 계속 더하여 전체 총합을 만들어 낸다. 이때 별도의 함수 객체를 지정하면 더하기가 아닌 다른 연산을 할 수도 있다. 예를 들어 accumulate(vi1.begin(), vi1.end(), 1, multiplies<int>()) 연산을 하면 모든 요소의 누적곱이 구해진다. 이때 초기값은 곱셈의 항등원인 1로 지정해야 할 것이다. 아무튼 accumulate는 구간의 모든 요소들에 대해 어떤 연산을 적용한 결과를 계산하며 디폴트 연산이 덧셈일 뿐이다.

다음 함수는 partial_sum 함수와 유사하게 동작하는데 인접 요소들의 차를 계산해 result 반복자에 차례대로 대입한다.

 

OutIt adjacent_difference(InIt first, InIt last, OutIt result [ ,BinOp op]);

 

아마 대충 어떤 동작을 하는지 상상이 갈 것이다. 예제로 동작을 확인해 보자.

 

: adjacent_difference

#include <iostream>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

 

template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";

      copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

 

void main()

{

     int ar[]={1,2,5,10,15,12,20};

     vector<int> vi(&ar[0],&ar[7]);

     vector<int> vi2;

     adjacent_difference(vi.begin(),vi.end(),back_inserter(vi2));

     dump ("부분차 ",vi2);

}

 

정수 벡터를 정의하고 이 벡터의 부분차를 새로운 벡터에 계산했다. 그림으로 요소들의 변화를 살펴보면 쉽게 이해할 수 있다.

첫 번째 요소는 그대로 내려오고 첫 번째 요소와 두 번째 요소의 차가 새 벡터의 두 번째 요소에 기록된다. 결과 벡터의 n번째 요소는 원본의 n-1 요소와 n 요소의 차이라고 할 수 있다. 만약 원본 벡터가 월별 판매량이었다면 결과 벡터는 그 달의 판매 증가량이라고 할 수 있다. result 반복자는 컨테이너 내부의 반복자일 수도 있으므로 차를 구해 곧바로 자신에게 다시 대입하는 것도 가능하다.