[STL] 수치 알고리즘

in STL



수치 알고리즘은 다른 알고리즘과 달리 <numeric> 헤더파일에 정의 된다. 순차열의 모든 원소에 대하여 누적을 구하거나 순서대로 원소에 연산을적용하고 싶을 때 수치 알고리즘을 사용하면 도움이 된다.

accumulate()

순차열의 모든 원소의 합을 구하고 싶을 때 사용한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	
	// 0+10+20+30+40+50의 합을 반환
	cout << accumulate(v.begin(), v.end(), 0) << endl;
	// 100+10+20+30+40+50의 합을 반환
	cout << accumulate(v.begin(), v.end(), 100) << endl;
}

image

결과가 직관적이므로 설명은 생략한다.

함수류 버전 accumulate()

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

template<typename T>
class Plus {
public:
	T operator () (const T& left, const T& right) {
		return left + right;
	}
};

void main() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	
	// 사용자 함수자 합 연산 0+1+2+3+4+5
	cout << accumulate(v.begin(), v.end(), 0, Plus<int>()) << endl;
	// plus 합 연산 0+1+2+3+4+5
	cout << accumulate(v.begin(), v.end(), 0, plus<int>()) << endl;
	// multiplies 곱 연산 1*1*2*3*4*5
	cout << accumulate(v.begin(), v.end(), 1, multiplies<int>()) << endl;
}

image

여기서 알고 넘어가야하는 것은 기본적으로 제공되는 plus와 muliplies를 사용했다는 것이다.

inner_product()

두 순차열의 내적(모든 원소의 곱의 합)을 구하고 싶을 때 사용한다. inner_product(b,e,b2,x)는 x의 초기값으로 구간 [b,e)의 원소와 구간 [b2,b2+(e-b))의 원소 내적을 반환한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);

	vector<int> v2;
	v2.push_back(2);
	v2.push_back(2);
	v2.push_back(2);
	v2.push_back(2);
	v2.push_back(2);

	// 0+ 1*2 + 2*2 + 3*2 + 4*2 +5*2
	cout << inner_product(v1.begin(), v1.end(), v2.begin(), 0);
	cout << endl;
	// 100+ 1*2 + 2*2 + 3*2 + 4*2 +5*2
	cout << inner_product(v1.begin(), v1.end(), v2.begin(), 100);
}

image

결과가 직관적이므로 설명은 생략한다.

함수류 버전 inner_product()

함수류 버전 inner_product()를 사용하면 원소간의 다양한 연산과 누적을 할 수 있다. inner_product(b,e,b2,x,f1,f2)는 f1이 + f2가 * 연산이면 구간 [b,e)의 원소 a1, a2, a3, 구간 [b2,b2+(e-b))의 원소 b1, b2, b3에 대해 x + a1*b1 +a2*b2 + a3*b3이다. 예시를 보자.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int Plus(int left, int right) {
	return left + right;
}

int Minus(int left, int right) {
	return left - right;
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(2);
	v2.push_back(2);
	v2.push_back(2);
	v2.push_back(2);
	v2.push_back(2);

	// 0 + (10-2) + (20-2) + (30-2) + (40-2) + (50-2) 사용자 정의 함수 사용
	cout << inner_product(v1.begin(), v1.end(), v2.begin(), 0, Plus,Minus) << endl;
	// 0 + (10-2) + (20-2) + (30-2) + (40-2) + (50-2) STL 함수자 사용
	cout << inner_product(v1.begin(), v1.end(), v2.begin(), 0, plus<int>(),minus<int>()) << endl;
}

image

결과가 직관적이므로 설명은 생략한다.

adjacent_difference()

순차열에서 원소 간의 차를 구하고 싶을 때 사용한다. p=adjacent_difference(b,e,t)는 구간 [b,e)의 반복자가 p일 때 (*p - *(p-1)) 연산을 목적지 순차열 [t,p)에 저장한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	vector<int> v2(5);

	vector<int>::iterator iter_end;
	iter_end = adjacent_difference(v1.begin(), v1.end(), v2.begin());

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
}

image

위 예시는 인접한 원소와의 차를 목적지 순차열에 저장하는 것이다.

함수류 버전 adjacent_difference()

순차열에서 인접 원소와의 사용자 정의 연산을 수행하려면 함수류 버전 adjacent_difference()를 사용한다.

p=adjacent_difference(b,e,t,f)는 구간 [b,e)의 반복자가 q라면 f(*q,*(q-1)) 연산을 목적지 순차열 [t,p)에 저장한다. 인접 원소의 합을 목적지 순차열에 저장하는 예시를 보자.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int Plus(int left, int right) {
	return left + right;
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	vector<int> v2(5);

	vector<int>::iterator iter_end;
	iter_end = adjacent_difference(v1.begin(), v1.end(), v2.begin(),Plus);

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
}

image

partial_sum()

순차열에서 현재 원소까지의 합을 구하고자 한다면 partial_sum()을 사용한다. p=partial_sum(b,e,t)는 구간 [b,e)의 현재 원소까지의 합(누적)을 목적지 순차열 [t,p)에 저장한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int Plus(int left, int right) {
	return left + right;
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	vector<int> v2(5);

	vector<int>::iterator iter_end;
	iter_end = partial_sum(v1.begin(), v1.end(), v2.begin());

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
}

image

함수류 버전 partial_sum()

순차열에서 현재 원소까지의 합(누적)뿐만아니라 사용자 연산을 수행하려면 함수류 버전의 partial_sum()을 사용하면 된다. p=partial_sum(b,e,t,f)는 구간 [b,e)의 현재 원소싸지의 f연산의 값을 목적지 순차열 [t,p)에 저장한다.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int Multi(int left, int right) {
	return left * right;
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	vector<int> v2(5);

	vector<int>::iterator iter_end;
	iter_end = partial_sum(v1.begin(), v1.end(), v2.begin(),Multi);

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
}

image

위 partial_sum()의 f가 Multi기 때문에 v1의 원소 10을 v2[0]에 저장하고, 10*20을 v2[1], 10*20*30*을 v2[2]에, 10*20*30*40을 v[3]에, 10*20*30*40*50을 v2[4]에 저장한다,


© 2022. by KSC

Powered by sora