Algorithm - 알고리즘

수치 알고리즘

다른 알고리즘과 달리 <numeric>헤더에 정의된다.

순차열의 모든 원소에 대해 누적을 구하거나 순서대로 원소에 연산을 적용해야할 때 사용하면 좋은 알고리즘이다.

알고리즘 함수	사용 형태 (인자)	역할	반환값
accumulate	accumulate(first, last, init) accumulate(first, last, init, op)	범위의 값을 왼쪽부터 누적합 또는 지정 연산 수행	누적 결과 값
inner_product	inner_product(first1, last1, first2, init) inner_product(first1, last1, first2, init, op1, op2)	두 범위의 각 원소 쌍을 곱하고 합산 (내적)	내적 결과 값
adjacent_difference	adjacent_difference(first, last, out) adjacent_difference(first, last, out, op)	인접한 원소 간 차이 또는 지정 연산 결과 복사	out 범위의 끝 반복자
partial_sum	partial_sum(first, last, out) partial_sum(first, last, out, op)	왼쪽부터 차례대로 부분 합 또는 지정 연산 누적 복사	out 범위의 끝 반복자

---

📌 accumulate()

순차열의 모든 원소의 합을 구할때 사용한다.

✅ accumulate() 일반 버전

accumulate(first, last, init) ➡ 구간 [first, last)의 모든 원소의 합 + 초기값을 반환

int main()
{
	vector<int>v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	// 0 + 10 + 20 + 30
	int sum = accumulate(v.begin(), v.end(), 0);

	cout << sum << endl; // 60
}  

✅ accumulate() 함수류 버전

함수 객체나 사용자 정의 함수를 사용하여 연산 조건을 지정할 수 있다.

accumulate(first, last, init, op) ➡ 모든 원소에 대해 op 연산을 진행한다.

int main()
{
	vector<int>v;

	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	// 1 * 2 * 3 * 4
	int sum = accumulate(v.begin(), v.end(), 1, multiplies<int>()); // 함수 객체 multiplies

	cout << sum << endl; // 24
}

---

📌 inner_product()

두 순차열의 내적을 구할 때 사용한다.
➡ 내적 : 각각의 원소를 곱한 후 모두 더한값

✅ inner_product() 일반 버전

내적 연산을 진행한다.

inner_product(first1, last1, first2, init)

➡ [first1, last1)구간의 원소와 [fisrt2, first2 + last1 - first1)구간의 원소 내적을 반환

➡ 두번째 구간 [first2, first2 + last1 - first1)의 의미는 first2 시작부터, first1 순차열의 크기만큼의 범위이다.

int main()
{
	vector<int>v1;

	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	vector<int>v2;

	v2.push_back(5);
	v2.push_back(10);
	v2.push_back(15);

	// 1 + (2 * 5) + (3 * 10) + (4 * 15)
	int sum = inner_product(v1.begin(), v1.end(), v2.begin(), 1); // 초기값 1

	cout << sum << endl; // 101
}  

✅ inner_product() 함수류 버전

inner_product(first1, last1, first2, init, op1, op2)

op1 ➡ 총 연산 함수 or 함수 객체
op2 ➡ 두 순차열끼리 연산 함수 or 함수 객체

int main()
{
	vector<int>v1;

	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	vector<int>v2;

	v2.push_back(5);
	v2.push_back(10);
	v2.push_back(15);

	// 1 + (2 - 5) + (3 - 10) + (4 - 15)
	int sum = inner_product(v1.begin(), v1.end(), v2.begin(), 1, plus<int>(), minus<int>()); // 초기값 1

	cout << sum << endl; // -20
}

---

📌 adjacent_difference()

순차열에서 인접한 원소 간의 차이를 구할 때 사용한다.

✅ adjacent_difference() 일반 버전

adjacent_difference(first, last, out) ➡ 모든 인접한 원소 간의 차이를 반환한다.

즉, [first, last)구간의 반복자가 p일 때 (*p - *(p - 1)) 연산을 목적지 순차열에 저장

int main()
{
	vector<int>v1;

	v1.push_back(2); // 원소간의 차이는 1
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);


	vector<int>v2(5); // 사이즈5

	adjacent_difference(v1.begin(), v1.end(), v2.begin());

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // v1[0]는 기존 원소값, 그 뒤 원소들은 원소간의 차 값
	}
	// 2 1 1 1 1
}

✅ adjacent_difference() 함수류 버전

누적값이 아닌 인접한 원소간의 연산이다.
아래의 코드에서는 plus<T>() 함수 객체를 사용하고 있으니, f(*p, *(p-1) 내부 연산이 +로 진행될 것이다.

즉, 인접한 원소간의 합을 반환하게 된다.

adjacent_difference(first, last, out, op)

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

int 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(5); // 사이즈5

	adjacent_difference(v1.begin(), v1.end(), v2.begin(), plus<int>());

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // v1[0]는 기존 원소값, 그 뒤 원소들은 원소간의 조건자 값
	}
	// 10 30 50 70 90
}

---

📌 partial_sum()

순차열에서 현재 원소까지의 합을 구할 때 사용한다. ➡ 누적합

✅ partial_sum() 일반 버전

partial_sum(first, last, out)

int 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(5); // 사이즈5

	partial_sum(v1.begin(), v1.end(), v2.begin()); // v2에 누적합 저장

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // v2[0]는 기존 원소 값 
	}

	// 10 30 60 100 150
}

✅ partial_sum() 함수류 버전

partial_sum(first, last, out, op) ➡ 원하는 op 함수를 사용하여 조건을 변경할 수 있다.

아래의 코드에서는 multiplies<T>() 함수 객체를 사용해서 '현재 원소까지의 곱'을 반환한다.

int 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(5); // 사이즈5

	partial_sum(v1.begin(), v1.end(), v2.begin(), multiplies<int>()); // v2에 누적곱 저장

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // v2[0]는 기존 원소 값 
	}

	// 10 200 6000 240000 12000000
}