_C++_알고리즘_Part_3

검색 알고리즘

검색 알고리즘은 STL 컨테이너의 항목열을 대상으로 특정 항목을 찾는 함수이다.

모든 알고리즘은 operator== 또는 operator<의 디폴트 연산자를 사용하는데, 필요하다면 비교 콜백 함수를 직접 전달 할 수 있도록 오버로딩 되어 있다.

---

find(), find_if()

주어진 값과 같거나, 주어진 조건이 true가 되는 첫 번째 항목을 찾아주며 선형 시간 복잡도를 갖는다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int arr[5] = { 1, 2, 3, 4, 5 };
	auto ptr = find(arr, arr + 5, 3);//반복자 대신 배열의 항목을 가리키는 포인터도 가능
	cout << *ptr << endl;

	vector<int> v{ -1, -4, 6, 2, 20 };
	auto vIter = find_if(v.begin(), v.end(), [](int a) {
		return a > 10;
		});
	//cout << *vIter << endl;
	cout << boolalpha << (vIter != v.end()) << endl; // 조건에 맞는 값이 있는지 없는지 확인
}

 

min_element(), max_element(), minmax_element()

• min_element(): 최솟값
• max_element(): 최댓값
• minmax_element(): 최솟값, 최댓값의 쌍

선형시간 복잡도를 가진다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v { 1, 2, 3, 4, 5 };
	auto minIter = min_element(v.begin(), v.end());
	cout << *minIter << endl;

	auto maxIter = max_element(v.begin(), v.end());
	cout << *maxIter << endl;

	auto min_maxIter = minmax_element(v.begin(), v.end());
	cout << *min_maxIter.first << " " << *min_maxIter.second << endl;
	return 0;
}

 

binary_search(), lower_bound(), upper_bound(), equal_range()

이 함수들은 이미 정렬된 항목열을 대상으로 한다.

vector, deque, array, 배열에서 유용하게 사용이 된다. (로그 시간 복잡도를 가진다.)

list에서도 사용할 수 있지만, 랜덤 액세스 반복자를 지원하지 않아서 선형 시간 복잡도로 성능이 떨어진다.

 

1. binary_search()

주어진 항목열에 특정 값이 있는지 없는지 여부를 bool타입으로 반환해준다.

lower_bound(), upper_bound(), equal_range()는 특정 값을 기준으로 항목을 찾아 반복자를 반환한다.

2. lower_bound()

주어진 값보다 같거나 큰 숫자의 반복자를 반환해준다.

ex) {1,2,2,3,5}와 같은 항목열에서 2를 찾는다면 두 번째 항목을 가리키는 반복자를 반환해준다.

4를 찾는다면 4가 5보다 작지 않으므로, 마지막 항목을 가리키는 반복자를 반환해준다.

주어진 값이 마지막 항목보다 크다면 end 반복자를 반환해줍니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v { 1, 2, 2, 3, 5 };
	auto lower_b = lower_bound(v.begin(), v.end(), 2);
	cout << *lower_b << endl;
	
	return 0;
}

 

 

3. upper_bound()

주어진 값보다 큰 첫 번째 항목을 가리키는 반복자를 반환해준다.

ex) {1,2,2,3,5}와 같은 항목열에서 2를 찾는다면 네 번째 항목을 가리키는 반복자를 반환해준다.

4를 찾는다면 4가 5보다 큰 값이므로, 마지막 항목을 가리키는 반복자를 반환해준다.

주어진 값이 마지막 항목보다 크다면 end 반복자를 반환해줍니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v { 1, 2, 2, 3, 5 };
	auto lower_b = upper_bound(v.begin(), v.end(), 2);
	cout << *lower_b << endl;
	
	return 0;
}

 

4. equal_range()

lower_bound() 결과와 upper_bound() 결과를 pair로 묶어서 같이 반환해준다.

 

유틸리티 알고리즘

min, max, minmax 가 있으며 이들은 STL 알고리즘 함수들과 달리 반복자를 사용하지 않는다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int a = 3;
	int b = 10;
	
	cout << min(a, b) << endl;
	cout << max(a, b) << endl;
	cout << minmax(a, b).first << " " << minmax(a, b).second << endl; // min, max를 페어로 출력
	
	return 0;
}