[STL] 변경 알고리즘

in STL



변경 알고리즘은 순차열의 원소를 서로 교환하거나 이동하여 순차열 원소의 순서를 변경하는 알고리즘이다.

next_permutation()

원소의 순서를 순열처럼 변경할 때 사용한다. next_permutation(b,e)는 구간 [b,e)의 순차열을 다음 순열(사전순)의 순차열이 되게 한다.마지막 순열이면 false, 아니면 true를 반환한다. 예시를 보자.

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	// v의 모습 10 20 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;
	// 마지막 순차열이므로 false 반환
	cout << next_permutation(v.begin(), v.end()) << endl;
	cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
}

image-20220324083505001

사용자 조건으로 순열 만들기

사용자 조건으로도 순열을 만들 수 있다. 예시를 보자.

#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& os, const Point& arg) {
	os << "(" << arg.GetX() << ", " << arg.GetY() << ")";
	return os;
}

bool Pred(const Point& left, const Point& right) {
	return left.GetY() < right.GetY();
}

void main() {
	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;
	// 마지막 순차열이므로 false 반환
	cout << next_permutation(v.begin(), v.end(), Pred) << endl;
	cout << "v : " << v[0] << " " << v[1] << " " << v[2] << endl;
}

image

prev_permutation()

prev_permutation()은 순열의 처음일 때 false를 반환하고, 순차열의 이전 순열을 만든다. 사용법은 next_permutation()과 같으니 설명은 생략한다.

partition()

순차열의 원소를 특정 조건에 따라 분류하고자 할 때 사용한다. p=partition(b,e,f) 알고리즘은 순차열의 반복자를 q라 할 때 f(*q)를 만족하는 원소는 구간 [b,p)에 만족하지 않는 원소는 [p,e)에 넣는다. 예시를 보자.

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

bool Pred(int n) {
	return n < 40;
}

void main() {
	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);
	// v의 모습 30 40 50 10 20 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 << "[v.begin(),iter_sep)의 순차열(40 미만) : ";
	for (vector<int>::iterator iter = v.begin(); iter != iter_sep; iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "[iter_sep,v.end())의 순차열(40이상) : ";
	for (vector<int>::iterator iter = iter_sep; iter != v.end(); iter++) {
		cout << *iter << " ";
	}
}

image

결과를 보면 알 수 있듯이 원소의 상대적인 순서까지 바뀌어 버린다. 하지만 원소의 상대적인 순서는 바꾸지 않고 특정 기준으로 원소를 분류하고 싶다면 stable_partition()을 사용한다.

stable_partition()

원소의 상대적인 순서는 바꾸지 않고 특정 기준으로 원소를 분류하고 싶다면 stable_partition()을 사용한다.

예시를 보자.

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

bool Pred(int n) {
	return n < 40;
}

void main() {
	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);
	// v의 모습 30 40 50 10 20 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 = stable_partition(v.begin(), v.end(), Pred);
	cout << "[v.begin(),iter_sep)의 순차열(40 미만) : ";
	for (vector<int>::iterator iter = v.begin(); iter != iter_sep; iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "[iter_sep,v.end())의 순차열(40이상) : ";
	for (vector<int>::iterator iter = iter_sep; iter != v.end(); iter++) {
		cout << *iter << " ";
	}
}

image

결과에서 알 수 있듯이 10,20 둘 다 40미만의 원소이지만 저장 될 때 원래 순차열의 상대적인 순서를 지켜서 30 10 20으로 들어간다.

random_shuffle()

순차열의 원소를 랜덤으로 섞고싶을 떄 사용한다. 예시를 보자.

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 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] << " ";
	}
}

image-20220324091928399

하지만 문제점이 있다. 분명 랜덤하게 섞으라고 했는데 처음에는 섞이지만 계속해서 컴파일하면 같은 결과가 나온다. 이유는 이렇다 기본 랜덤기의 시작값(seed)이 srand(1)이기 때문이다. 출력 결과를 바꾸고 싶다면 헤더파일 <cstdlib>를 선언하고 srand()를 사용한다. 위 코드를 조금 수정해보자.

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

void main() {
	srand(time(NULL));
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 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] << " ";
	}
}

결과는 계속해서 바뀐다.

reverse()

순차열의 순서를 뒤집고 싶을 때 사용한다.

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 50

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	reverse(v.begin(), v.end());
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

image

reverse_copy()

뒤집힌 순차열을 목적지 순차열에 복사하고 싶을 때 사용한다. 예시를 보자.

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 50

	vector<int> v2(5);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	vector<int>::iterator iter_end;
	iter_end=reverse_copy(v.begin(), v.end(),v2.begin());

	cout << "[v2.begin(),iter_end)의 순차열 : ";
	for (vector<int>::iterator iter = v2.begin(); iter != iter_end;iter++) {
		cout << *iter << " ";
	}
}

image

결과와 같이 p=reverse_copy(b,e,t)알고리즘은 구간 [b,e)의 순차열을 뒤집고 목적지 순차열 [t,p)에 저장한다.

주의 할 점은 목적지 순차열에 복사할 때 덮어쓰기로 동작하기 때문에 목적지 순차열의 원본 순차열보다 원소의 개수가 많거나 같아야 한다.

rotate()

순차열을 회전 시키고 싶을 때 사용한다. rotate(b,m,e) 알고리즘은 첫 원소와 마지막 원소가 연결된 것처럼 지정된 횟수 만큼 오른쪽이나 왼쪽으로 회전 시킨다.

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 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;
	// 모든 원소를 왼쪽으로 2만큼 회전
	rotate(v.begin(), middle,v.end());
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

image

결과와 같이 모든 원소가 왼쪽으로 2만큼 씩 회전한 것을 볼 수 있다. 오른쪽으로 회전하는 예시를 보겠다.

오른쪽 회전

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 50

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	// 모든 원소를 오른쪽으로 2만큼 회전
	rotate(v.begin(),v.end()-2, v.end());
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}

image

즉, rotate() 알고리즘은 2번째 인자에 v.begin()+m : m만큼 왼쪽으로 회전 / v.end()-m : 오른쪽으로 m만큼 회전 이렇게 생각하면 된다.

rotate_copy()

순차열을 지정된 횟수만큼 회전시키고 목적지 순차열로 복사하고 싶을 때 사용한다. 예시를 보자.

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 20 30 40 50

	vector<int> v2(5);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	vector<int>::iterator iter_end;

	// 모든 원소를 왼쪽으로 2만큼 회전 후 [v2.begin(),iter_end)에 복사
	iter_end=rotate_copy(v.begin(),v.begin()+2, v.end(),v2.begin());
	cout << "v2 : ";
	for (vector<int>::iterator iter = v2.begin(); iter !=iter_end; iter++) {
		cout <<*iter << " ";
	}
	cout << endl;
}

image


© 2022. by KSC

Powered by sora