본문 바로가기
알고리즘/기본

[C++/STL] Algorithm

by E145 2020. 6. 14.
반응형

0. C++ STL - Algorithm

 

 - 헤더 선언 필요( #include <algorithm> )

 

 

1. 정렬

 

정렬 함수

 - 일반적인 정렬 함수

 

 - O(nlogn) 보장

 

 - sort(원소 시작 위치 반복자 ,원소 마지막 다음 위치 반복자 , 비교함수) 

 

 - 예시(오름차순)

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 5,6,8,12,3,9,1,30 };

	cout << "정렬 전 : " << endl;
	for (auto i : vec)
		cout << i <<", ";
	cout << endl;

	// 기본 오름차순
	sort(vec.begin(), vec.end());

	cout << "정렬 후 : " << endl;
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;

	return 0;
}

오름차순 결과 화면

 

 - 예시(내림차순)

#include <algorithm>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 5,6,8,12,3,9,1,30 };

	cout << "정렬 전 : " << endl;
	for (auto i : vec)
		cout << i <<", ";
	cout << endl;

	// 내림 차순
	sort(vec.begin(), vec.end(), greater<int>());

	cout << "정렬 후 : " << endl;
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;

	return 0;
}

내림차순 결과 화면

 

 - 예시(사용자 지정 비교함수)

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

using namespace std;

struct points {
	int x;
	int y;
};

bool comp(points &p1, points &p2) {
	
	// 내림차순 p1.x > p2.x
	// 오름차순
	return p1.x < p2.x;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<points> vec;

	vec.push_back({ 0,3 });
	vec.push_back({ 10,3 });
	vec.push_back({ 6,3 });
	vec.push_back({ 7,3 });
	vec.push_back({ 12,3 });
	vec.push_back({ -3,3 });

	cout << "정렬 전 : " << endl;
	for (auto i : vec)
		cout << i.x <<", ";
	cout << endl;
    
	// 사용자 임의 함수 사용
	sort(vec.begin(), vec.end(), comp);

	cout << "정렬 후 : " << endl;
	for (auto i : vec)
		cout << i.x << ", ";
	cout << endl;

	return 0;
}

오름차순 사용자 함수 결과 화면

 

 

 

부분 정렬

 

 - 일부만 정렬

 

 - partial_sort(start, middle, end)

   (start, middle] 범위만 정렬, 나머지는 랜덤

 

 - 전체가 N이고, 정렬 부분이 M이라면 시간복잡도는 O(NlogM)이다

 

 - 예시

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 6,2,4,3,5,8,10 };

	cout << "정렬 전 : " << endl;
	for (auto i : vec)
		cout << i <<", ";
	cout << endl;
	
    // 0, 1, 2, 3 까지만 정렬
	partial_sort(vec.begin(),vec.begin()+3, vec.end());

	cout << "정렬 후 : " << endl;
	for (auto i : vec)
		cout << i<< ", ";
	cout << endl;

	return 0;
}

실행 결과

 

 

stable_sort

 

 - 정렬은 하지만, 원소들 간 순서는 유지한다.

 

 - O(nlogn)인 sort와 달리 최악의 경우 O(n$(logn)^2$)

 

 

최대, 최소

 

최대, 최소 값

 

 - min(값1, 값2), max(값1, 값2)

 

 - 매개변수 2개 중 작은 값, 큰 값 출력

 

 - 예시

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cout << "min : "<< min(10, 3) << endl;

	cout << "max : " << max(10, 3) << endl;

	return 0;
}

결과 화면

 

 

구간 최대, 최소

 

 - 구간 중 최대, 최소 값의 이터레이터 반환

 

 - 랜덤 액세스인 list, vector 에서만 사용 가능하다.

 

 - 예시

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 1,6,10,2,7,3 };

	// 이터레이터를 반환하기 때문에 값을 사용하기 위해서 * 사용
	cout << "min : "<< *min_element(vec.begin(),vec.end()) << endl;

	cout << "max : " << *max_element(vec.begin(), vec.end()) << endl;

	return 0;
}

실행 결과

 

 

 

 

제거

 

범위 내 원소 제거

 - vec.erase(시작 위치, 끝 위치)

 

 - 범위에 있는 원소 제거

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 1,6,10,2,7,3 };

	cout << " 제거 전 : ";
	for (int i : vec)
		cout << i << ", ";
	cout << endl;

	vec.erase(vec.begin()+3, vec.end());

	cout << " 제거 후 : ";
	for (int i : vec)
		cout << i << ", ";
	cout << endl;

	return 0;
}

실행 결과

 

 

 

특정 원소 제거

 

 - remove 이용 해당 원소를 뒤로 미룬 후 erase를 이용하여 제거.

 

 - vector, list, map, set 등 에서 사용 가능

 

 - 예시

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 1,6,10,2,7,3 };

	cout << " 제거 전 : ";
	for (int i : vec)
		cout << i << ", ";
	cout << endl;

	vec.erase(remove(vec.begin(), vec.end(), 10), vec.end());

	cout << " 제거 후 : ";
	for (int i : vec)
		cout << i << ", ";
	cout << endl;

	return 0;
}

실행 결과

 

 

 

 

중복 원소 제거

 

 - unique를 이용하여 중복 원소를 뒤로 보내고, erase를 이용하여 제거

 

 - unique는 반드시 정렬되어 있어야 한다.

 

 - 예시

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 1,3,1,3,7,3 };
    
	// 정렬 필요
	sort(vec.begin(), vec.end());

	cout << " 제거 전 : ";
	for (int i : vec)
		cout << i << ", ";
	cout << endl;

	vec.erase(unique(vec.begin(), vec.end()), vec.end());

	cout << " 제거 후 : ";
	for (int i : vec)
		cout << i << ", ";
	cout << endl;

	return 0;
}

실행 결과

 

 

 

개수 

 

 - 범위 내의 원소 중 값과 일치하는 개수를 반환

 

 - 예시

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 1,3,1,3,7,3,3 };

	cout << "3의 개수 : " << count(vec.begin(), vec.end(), 3) << endl;

	return 0;
}

 

탐색

 

Binary_Search

 

 - 정렬되어 있는 데이터를 이진 탐색으로 원하는 값을 찾을 수 있다.

 

 - 예시

 

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> v{ 1,5,6,25,2,111,4 };

	sort(v.begin(), v.end());

	cout << "벡터에 25가 있는가 ? " << binary_search(v.begin(), v.end(), 25) << endl;

	cout << "벡터에 77가 있는가 ? " << binary_search(v.begin(), v.end(), 77) << endl;

	return 0;
}

 

 

lower_bound, upper_bound

 

 - 정렬되어 있는 데이터를 이진 탐색으로 원하는 값을 찾을 수 있다.

 

 - lower_bound 는 찾는 값 >= 기준 값 중 가장 작은 원소를 반환

 

 - upper_bound는 찾는 값 > 기준 값 중 가장 작은 원소를 반환.

 

 - lower_bound, upper_bound의 차이점은 기준 값을 포함하는가 이다.

 

 - lower_bound, upper_bound 모두 iterator를 반환한다.

 

 - 예시

 

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> v{ 1,5,6,25,2,111,4 };

	sort(v.begin(), v.end());

	for (auto a : v)
		cout << a << " ";
	cout << endl <<endl ;

	cout << "== 값이 존재하는 경우 ==" << endl << endl;;

	cout << "lower_bound(25) : 인덱스 = " << lower_bound(v.begin(), v.end(), 25)-v.begin() 
    	<< " 값 = "<< *lower_bound(v.begin(), v.end(), 25) << endl;

	cout << "upper_bound(25) : 인덱스 = " << upper_bound(v.begin(), v.end(), 25) - v.begin() 
    	<< " 값 = " << *upper_bound(v.begin(), v.end(), 25) << endl;

	cout << endl << "== 값이 존재하지 않는 경우 ==" << endl << endl;;

	cout << "lower_bound(28) : 인덱스 = " << lower_bound(v.begin(), v.end(), 28) - v.begin() 
    	<< " 값 = " << *lower_bound(v.begin(), v.end(), 28) << endl;

	cout << "upper_bound(28) : 인덱스 = " << upper_bound(v.begin(), v.end(), 28) - v.begin() 
    	<< " 값 = " << *upper_bound(v.begin(), v.end(), 28) << endl;

	return 0;
}

 

 

 

순열

 

 - next_permutation을 이용하여 오름차순의 모든 순열을 표현할 수 있다.

 

 - prev_permutation을 이용하여 내림차순의 모든 순열을 표현할 수 있다.

 

 - 순서대로 정렬되어 있어야 정확한 순열을 구할 수 있다.

   (1, 4, 3, 2와 같이 정렬되어 있다면, 정확한 모든 순열을 구할 수 없다.)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> v{ 1,2,5,7 };

	// 오름차순
	do {
		for (auto n : v)
			cout << n << " ";
		cout << endl;
	} while (next_permutation(v.begin(), v.end()));


	return 0;
}

 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> v{ 7,5,2,1 };
	
    // 내림차순
	do {
		for (auto n : v)
			cout << n << " ";
		cout << endl;
	} while (prev_permutation(v.begin(), v.end()));


	return 0;
}

 

 

반응형
저작자표시

'알고리즘 > 기본' 카테고리의 다른 글

Java 코테용 정리  (0) 2021.04.03
비트마스크  (0) 2020.11.30
[C++/STL] 셋(Set), 맵(Map)  (1) 2020.06.07
[C++/STL] 페어(Pair)  (0) 2020.06.07
[C++/STL] 덱(Deque)  (0) 2020.06.07

관련글

댓글

티스토리툴바