도순씨의 코딩일지
C++ :: STL 변경 알고리즘 & 정렬 알고리즘 본문
🌼 변경 알고리즘
변경 알고리즘 은 순차열의 원소를 서로 교환하거나 이동하여 순차열 원소의 순서를 변경시켜줍니다.
원소의 순서를 순열(permutation)처럼 변경할 때 next_permutation()과 prev_permutation 알고리즘을 사용합니다.
10, 20, 30의 순차열을 사전순 순열로 만들어 출력하는 next_permutation() 알고리즘 예제입니다.
⭐️ next_permutation() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end()) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end()) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end()) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end()) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end()) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end()) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
return 0;
}
|
cs |
⭐️ next_permutation() 알고리즘 실행결과
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
v : 10 20 30
1
v : 10 30 20
1
v : 20 10 30
1
v : 20 30 10
1
v : 30 10 20
1
v : 30 20 10
0
v : 10 20 30
|
cs |
다음 예제는 Point 객체의 y값을 기준으로 순열을 만들어 출력하는 next_permutation() 알고리즘입니다.
⭐️ 조건자 버전 next_permutation() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point{
int x, y;
public:
explicit Point(int _x = 0, int _y = 0) : x(_x), y(_y){}
int GetX() const {return x;}
int GetY() const {return y;}
};
ostream& operator << (ostream& out, const Point& arg){
out << "(" << arg.GetX() << "," << arg.GetY() << ")";
return out;
}
bool Pred(const Point& left, const Point& right){
return left.GetY() < right.GetY();
}
int main(void){
vector<Point> v;
v.push_back(Point(5, 1));
v.push_back(Point(7, 2));
v.push_back(Point(5, 3));
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end(), Pred) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end(), Pred) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end(), Pred) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end(), Pred) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end(), Pred) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
cout << next_permutation(v.begin(), v.end(), Pred) << endl;
cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
}
|
cs |
⭐️ 조건자 버전 next_permutation() 알고리즘 실행결과
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
v : (5,1) (7,2) (5,3)
1
v : (5,1) (5,3) (7,2)
1
v : (7,2) (5,1) (5,3)
1
v : (7,2) (5,3) (5,1)
1
v : (5,3) (5,1) (7,2)
1
v : (5,3) (7,2) (5,1)
0
v : (5,1) (7,2) (5,3)
|
cs |
partition() 알고리즘 은 순차열의 원소를 특정 조건에 따라 분류하는 것입니다.
다음 예제는 40원소를 기준으로 작은 것과 큰 것을 구문하는 partition() 알고리즘 예제입니다.
⭐️ partition() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool Pred(int n){
return n < 40;
}
int main(void){
vector<int> v;
v.push_back(30);
v.push_back(40);
v.push_back(50);
v.push_back(10);
v.push_back(20);
v.push_back(60);
cout << "v : ";
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
vector<int>::iterator iter_sep;
iter_sep = partition(v.begin(), v.end(), Pred);
cout << "40 미만의 순차열: ";
for(vector<int>::iterator iter = v.begin() ; iter != iter_sep ; ++iter)
cout << *iter << " ";
cout << endl;
cout << "40 이상의 순차열: ";
for(vector<int>::iterator iter = iter_sep ; iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
}
|
cs |
⭐️ partition() 알고리즘 실행결과
|
1
2
3
|
v : 30 40 50 10 20 60
40 미만의 순차열: 30 20 10
40 이상의 순차열: 50 40 60
|
cs |
random_shuffle() 은 순차열 원소의 순서를 랜덤으로 뒤섞고자 할 때 사용됩니다.
⭐️ random_shuffle 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
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;
random_shuffle(v.begin(), v.end());
cout << "v : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
random_shuffle(v.begin(), v.end());
cout << "v : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ random_shuffle 알고리즘 실행결과
|
1
2
3
|
v : 10 20 30 40 50
v : 50 40 10 30 20
v : 20 50 30 40 10
|
cs |
다음 예제는 v 순차열을 왼쪽으로 2만큼 회전하는 rotate() 예제입니다.
⭐️ rotate() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
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;
vector<int> :: iterator middle = v.begin() + 2;
rotate(v.begin(), middle, v.end());
cout << "v : ";
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ rotate() 알고리즘 실행결과
|
1
2
|
v : 10 20 30 40 50
v : 30 40 50 10 20
|
cs |
🌼 정렬 알고리즘
정렬 알고리즘(sorting algorithms)은 변경 알고리즘의 특수한 형태입니다.
다음은 자료구조로 힙을 만드는 make_heap() 예제입니다.
⭐️ make_heap() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
v.push_back(60);
cout << "v : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
make_heap(v.begin(), v.end());
cout << "v[힙생성] : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ make_heap() 알고리즘 실행결과
|
1
2
|
v : 10 20 30 40 50 60
v[힙생성] : 60 50 30 40 20 10
|
cs |
다음 예제는 힙의 원소를 제거하는 pop_heap() 예제입니다.
⭐️ pop_heap() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
v.push_back(60);
make_heap(v.begin(), v.end());
cout << "v[힙 생성] : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++ i)
cout << v[i] << " ";
cout << endl;
pop_heap(v.begin(), v.end());
cout << "v[힙 삭제] 연산 수행 : ";
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ pop_heap() 알고리즘 실행결과
|
1
2
|
v[힙 생성] : 60 50 30 40 20 10
v[힙 삭제] 연산 수행 : 50 40 30 10 20 60
|
cs |
다음 예제는 힙을 정렬하는 sort_heap() 알고리즘 예제입니다.
⭐️ sort_heap() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
v.push_back(60);
make_heap(v.begin(), v.end());
cout << "v[힙 생성] : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++ i)
cout << v[i] << " ";
cout << endl;
sort_heap(v.begin(), v.end());
cout << "v[힙 정렬] 연산 수행 : ";
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ sort_heap() 알고리즘 실행결과
|
1
2
|
v[힙 생성] : 60 50 30 40 20 10
v[힙 정렬] 연산 수행 : 10 20 30 40 50 60
|
cs |
nth_element() 는 순차열의 원소 중 n개의 원소를 선별합니다.
⭐️ nth_element() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v;
for(int i = 0 ; i < 100 ; ++i)
v.push_back(rand() % 1000);
// 상위 20개의 원소 추출
nth_element(v.begin(), v.begin()+20, v.end());
cout << "v[상위 20개] : ";
for(vector<int>::size_type i = 0 ; i < 20 ; ++i)
cout << v[i] << " ";
cout << endl;
cout << "v[하위 80개] : ";
for(vector<int>::size_type i = 20; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ nth_element() 알고리즘 실행결과
|
1
2
|
v[상위 20개] : 1 123 73 105 94 115 63 13 24 124 91 97 99 42 144 165 153 149 169 157
v[하위 80개] : 188 195 194 196 298 451 492 278 404 335 249 337 303 267 272 425 298 438 228 408 490 327 393 336 485 357 228 440 501 503 987 672 708 944 668 967 709 745 530 903 722 666 549 923 801 853 977 821 579 933 979 981 635 878 865 814 544 536 633 669 810 930 629 512 517 826 658 816 933 560 709 612 505 882 752 566 716 840 729 807
|
cs |
다음은 sort() 함수를 이용하여 랜덤함수 100개를 정렬하는 예제입니다.
⭐️ sort() 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool Greater(int left, int right){
return left > right;
}
int main(void){
vector<int> v;
for(int i = 0 ; i < 100 ; ++i)
v.push_back(rand() % 1000);
cout << "v[정렬 전] : ";
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
sort(v.begin(), v.end());
cout << "v[정렬 less] : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
sort(v.begin(), v.end(), Greater);
cout << "v[정렬 greater] : ";
for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
return 0;
}
|
cs |
⭐️ sort() 알고리즘 실행결과
|
1
2
3
|
v[정렬 전] : 807 249 73 658 930 272 544 878 923 709 440 165 492 42 987 503 327 729 840 612 303 169 709 157 560 933 99 278 816 335 97 826 512 267 810 633 979 149 579 821 967 672 393 336 485 745 228 91 194 357 1 153 708 944 668 490 124 196 530 903 722 666 549 24 801 853 977 408 228 933 298 981 635 13 865 814 63 536 425 669 115 94 629 501 517 195 105 404 451 298 188 123 505 882 752 566 716 337 438 144
v[정렬 less] : 1 13 24 42 63 73 91 94 97 99 105 115 123 124 144 149 153 157 165 169 188 194 195 196 228 228 249 267 272 278 298 298 303 327 335 336 337 357 393 404 408 425 438 440 451 485 490 492 501 503 505 512 517 530 536 544 549 560 566 579 612 629 633 635 658 666 668 669 672 708 709 709 716 722 729 745 752 801 807 810 814 816 821 826 840 853 865 878 882 903 923 930 933 933 944 967 977 979 981 987
v[정렬 greater] : 987 981 979 977 967 944 933 933 930 923 903 882 878 865 853 840 826 821 816 814 810 807 801 752 745 729 722 716 709 709 708 672 669 668 666 658 635 633 629 612 579 566 560 549 544 536 530 517 512 505 503 501 492 490 485 451 440 438 425 408 404 393 357 337 336 335 327 303 298 298 278 272 267 249 228 228 196 195 194 188 169 165 157 153 149 144 124 123 115 105 99 97 94 91 73 63 42 24 13 1
|
cs |
📚 출처
공동환(2012), 뇌를 자극하는 C++ STL, 한빛미디어.
'𝐏𝐑𝐎𝐆𝐑𝐀𝐌𝐌𝐈𝐍𝐆 > 𝐂++' 카테고리의 다른 글
| C++ :: STL 수치 알고리즘 (0) | 2020.09.28 |
|---|---|
| C++ :: STL 정렬된 범위 알고리즘 (0) | 2020.09.27 |
| C++ :: STL 원소를 수정하는 알고리즘 & 제거 알고리즘 (0) | 2020.09.24 |
| C++ :: STL 원소를 수정하지 않는 알고리즘 (0) | 2020.09.23 |
| C++ :: STL map, multimap 컨테이너 (0) | 2020.09.19 |
Comments