알고리즘 관련 함수 1

1. partial_sum

---

연속된 구간의 합을 구해주는 함수

• numeric 헤더를 include 해주어야 사용 가능하다.
• [] 연산자를 통해 특정 구간까지의 합을 구할 수 있다.

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

int main()
{
	vector<int> vec = { 1,2,3,4,5 };
	vector<int> vec_sum(vec.size());

	partial_sum(vec.begin(), vec.end(), vec_sum.begin());

	for (const int& v : vec_sum)
	{
		cout << v << " "; //1 3 6 10 15
	}
    
      cout << vec_sum[0] << "\n"; // 1
      cout << vec_sum[2] << "\n"; // 1 + 2 + 3 = 6
      
      cout << vec_sum[4] - vec_sum[1] << "\n"; //15 - 3 = 12
      
      //cout << vec_sum[5];// out of range error
}

 

 

2. unique

---

중복된 원소를 제거한 후 끝 위치를 반환하는 함수

unique 결과값이 중복을 제거하고 정렬된 맨 값들을 제외하고 맨 처음 원소를 가리킨다.

아래 예시의 경우 {1,2,3,4,5, ?, ?, ?, ?, ?, ?, ?} 로 만들고, 첫번째 ?의 위치를 가리키는 것이 it이 된다.

• algorithm 헤더 include 필요
• 주의점) 제거할 배열이 정렬된 상태여야 한다!

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

int main()
{
	//already sorted
	vector<int> vec = { 1,2,2,2,3,3,3,4,4,5,5,5 };
	
	vector<int>::iterator it = unique(vec.begin(), vec.end());
	vec.erase(it, vec.end());

	for (const int& v : vec)
	{
		cout << v << " "; //1 2 3 4 5
	}
}

 

 

3. accumulate

---

총합을 구하는데 사용하는 함수

4번째 인자를 통해 내가 원하는 연산도 가능하다

• numeric 헤더 include 해야 한다.
• 세번째 인자는 값을 계산할 초기 수이다.
  • 예를 들어, 더하기에서는 0 곱하기에서는 1
• 네번째 인자를 통해 다양한 연산이 가능하다.
  • multiplies<> 를 통한 곱
  • 람다식을 통한 커스텀 연산 가능

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

int main()
{
	vector<int> vec = { 1,2,3,4,5 };

	int sum = accumulate(vec.begin(), vec.end(), 0);
	cout << sum << "\n"; // 15

	int mult = accumulate(vec.begin(), vec.end(), 1, multiplies<int>());
	cout << mult << "\n"; // 120

	int custom = accumulate(vec.begin(), vec.end(), 0, [](int a, int b) {return a + b + 2; });
	cout << custom << "\n"; //25
}

 

 

4. transform

---

참고1) transform에 관해서 이전에 정리했던 글

https://gbleem.tistory.com/21

string 관련 함수들 (tolower, isalpha, transform)

참고2) 람다에 관해서 이전에 정리했던 글

https://gbleem.tistory.com/22

Lambda Expressions

 

구간 내 원소들을 내가 원하는대로 변환시켜주는 함수

단항 연산과 이항 연산이 가능

• algorithm 헤더 include 필요
• 단항 연산 : 각 원소를 하나씩 변환 (제곱하기, N배 하기 등)
• 이항 연산 : 두 구간의 원소들을 짝지어서 변환 (둘이 더하기, 곱하기 등)

4 - 1. 단항 연산

• 첫번째 파라메터: 변환할 원소들의 입력 구간 시작
• 두번째 파라메터: 변환할 원소들의 입력 구간 끝
• 세번째 파라메터 : 변환된 원소들을 저장할 구간 시작 위치
• 네번째 파라메터 : 각 원소에 적용할 변환 함수

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

int main()
{
	vector<int> vec1 = { 1,2,3,4,5 };
	vector<int> vec1_res(vec1.size());

	transform(vec1.begin(), vec1.end(), vec1_res.begin(), [](int x) {return x * x; });

	for (const int& v : vec1_res)
	{
		cout << v << " "; //1 4 9 16 25
	}
}

4 - 2. 이항 연산

• 첫번째 파라메터: 변환할 원소들의 입력 구간 첫번째 시작점
• 두번째 파라메터: 변환할 원소들의 입력 구간 끝
• 세번째 파라메터 : 변환할 원소들의 입력 구간의 두번째 시작점
• 네번째 파라메터 : 변환된 원소들을 저장할 구간 시작 위치
• 다섯번째 파라메터 : 두 원소에 적용할 이항 연산 함수

주의할 점)

• 첫번째, 두번째 파라메터로 사용하는 입력 구간의 크기가, 세번째 입력 구간의 크기보다 작아야 한다.
• 아래 예시에서 vec2의 크기가 vec1보다 더 큰 경우 에러가 발생한다.

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

int main()
{
	vector<int> vec1 = { 1,2,3,4,5 };
	vector<int> vec2 = { 10,20,30, 40, 50 };
	vector<int> vec2_res(vec2.size());

	transform(vec2.begin(), vec2.end(), vec1.begin(), vec2_res.begin(), plus<int>());

	for (const int& v : vec2_res)
	{
		cout << v << " "; //11 22 33 44 55
	}
}

 

 

5. 문제

---

N개의 정수로 이루어진 정렬된 수열에서 A 이상 B이하인 원소의 개수를 출력하기

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

int main()
{		
	int n;
	cin >> n;

	vector<int> vec;
	for (int i = 0; i < n; ++i)
	{
		int num;
		cin >> num;
		vec.push_back(num);
	}

	int q;
	cin >> q;
	while (q--)
	{
		int a, b;
		cin >> a >> b;

		int st = lower_bound(vec.begin(), vec.end(), a) - vec.begin(); //a 이상인 최초의 수
		int en = upper_bound(vec.begin(), vec.end(), b) - vec.begin(); //b 초과인 최초의 수		

		cout << en - st << "\n";
	}
}