[STL] Algorithm - 변경 알고리즘

치치·2025년 7월 18일
stl

STL

목록 보기
18/21
post-thumbnail

Algorithm 알고리즘

변경 알고리즘

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

  • permutation 이 들어간 알고리즘들은 사전순 순열을 만든다.
    ➡ 사전 순 이란? 숫자나 문자가 작은 순서대로 나열되는 것

알고리즘 함수사용 형태 (인자)역할반환값
next_permutationnext_permutation(first, last)
next_permutation(first, last, comp)		현재 순열을 다음 순열로 바꿈다음 순열 존재 시 true, 없으면 false (마지막이면 초기 순열로 바뀜)
prev_permutationprev_permutation(first, last)
prev_permutation(first, last, comp)		현재 순열을 이전 순열로 바꿈이전 순열 존재 시 true, 없으면 false
partitionpartition(first, last, pred)조건을 만족하는 원소를 앞쪽으로 재배열 (순서는 보장 X)두 그룹의 경계 반복자
stable_partitionstable_partition(first, last, pred)조건 만족 원소를 순서 유지하며 앞쪽으로 재배열두 그룹의 경계 반복자
random_shuffle (C++11까지)random_shuffle(first, last)
random_shuffle(first, last, rand_gen)		원소들을 랜덤하게 섞음없음 (void)
reversereverse(first, last)범위의 원소들을 역순으로 바꿈없음 (void)
reverse_copyreverse_copy(first, last, result)원본은 유지하고, 결과 범위에 역순으로 복사복사된 결과의 끝 반복자
rotaterotate(first, middle, last)middle을 시작점으로 회전회전 후 새 첫 원소의 반복자
rotate_copyrotate_copy(first, middle, last, result)원본 유지, 회전 결과를 결과 범위에 복사복사된 결과의 끝 반복자


📌 next_permutation()

⭐ 쉽게 보자면, 반환 타입이 true라면 순차열을 사전순 순열로 만들어주고 true 타입을 반환하는 것 ⭐
⭐ 만약, 마지막 순차열이라면 false 타입 반환 후 원래의 첫 순열로 자동 정렬 되는 것 ⭐

✅ next_permutation(반복자 구간);

next_permutation()은 구간내의 요소들을 사전순으로 순열을 만든 뒤, bool 타입을 반환한다.
➡ 만약 마지막 순열에 도달했을 경우, false를 반환한 뒤 첫 순열로 자동 정렬된다.

예를 들어, 아래의 코드를 보았을 때 true일 경우만 while문을 반복한다.
➡ 마지막 순열 30 20 10을 출력하고 false가 반환된다. 여기서 다시 출력해보면 가장 처음 순차열로 자동 정렬된다.

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	// true 라면 반복
	while (next_permutation(v.begin(), v.end()))
	{
		for (int & a : v)
		{
			cout << a << " ";
		}
		cout << endl;
	}

	cout << "마지막 순열 30 20 10은 false 반환 후 첫 순열로 자동 정렬 : ";
	
	for (int& a : v)
	{
		cout << a << " ";
	}

	cout << endl;
}

✅ next_permutation(반복자 구간, 조건자);

위의 next_permutation()과 거의 동일하다. 조건자가 있다는 점만 다르다.

아래의 코드를 보면 Point()의 y를 기준으로 사전순 정렬이 된다.

class Point
{
	int x, y;

public:
	Point(int _x = 0, int _y = 0) : x(_x), y(_y) {  }
	int GetX() const { return x; }
	int GetY() const { return y; }
};

bool Calculate(const Point & left, const Point & right)
{
	// y값을 기준으로 순열 배치
	return left.GetY() < right.GetY();
}
int main()
{
	vector<Point> v;

	v.push_back(Point(5, 1));
	v.push_back(Point(7, 2));
	v.push_back(Point(5, 3));

	// true 라면 반복
	while (next_permutation(v.begin(), v.end(), Calculate))
	{
		for (Point & a : v)
		{
			cout << "(" << a.GetX() << "," << a.GetY() << ") ";
		}
		cout << endl;
	}

	cout << "마지막 순열 (5,3) (7,2) (5,1) 은 false 반환 후 첫 순열로 자동 정렬 : ";
	
	for (Point& a : v)
	{
		cout << a.GetX() << "," << a.GetY() << " ";
	}

	cout << endl;
}


📌 partition()

이전에 공부했던 QuickSort와 유사하다.
Quick Sort ➡ pivot 값을 기준으로 요소들을 순회하고 swap하는 방식
https://velog.io/@yangju058/알고리즘-Quick-Sort

✅ partition(반복자 구간, 조건자);

조건에 만족하는 원소들을 앞쪽에, 만족하지 않는 원소들을 뒤쪽에 배치한다.
➡ Quick Sort와 유사하게 조건에 만족하는 원소들의 위치를 변경시켜 배치한다.

아래의 코드에서 30 70 80 10 20 60 이 50을 기준으로 다시 배치된다.

30 70 80 10 20 60 ➡ 30 20 10 80 70 60
⭐이전 순차열의 상대적 순서를 따르지 않는다. 새로 배치된 순차열은 기존의 순서와 다르다.⭐
➡ 이전엔 10이 20보다 앞에왔지만, 다시 배치 후에는 20이 앞에 왔다.

bool Calculate(int n)
{
	return n < 50;
}
int main()
{
	vector<int> v;

	v.push_back(30);
	v.push_back(70);
	v.push_back(80);
	v.push_back(10);
	v.push_back(20);
	v.push_back(60);

	// 처음 상태
	for (int& a : v)
	{
		cout << a << " "; // 30 70 80 10 20 60
	}
	cout << endl;

	// 50미만이면 앞에, 50 이상이면 뒤에 배치
	partition(v.begin(), v.end(), Calculate);

	for (int& a : v)
	{
		cout << a << " "; // 30 20 10 80 70 60 
	}
}


📌 stable_partition()

✅ stable_partition(반복자 구간, 조건자);

일반 partition()에서 원소의 상대적인 순서는 변경하지 않고 유지할때 사용한다.

bool Calculate(int n)
{
	return n < 50;
}
int main()
{
	vector<int> v;

	v.push_back(30);
	v.push_back(70);
	v.push_back(80);
	v.push_back(10);
	v.push_back(20);
	v.push_back(60);

	// 처음 상태
	for (int& a : v)
	{
		cout << a << " "; // 30 70 80 10 20 60
	}
	cout << endl;

	// 50미만이면 앞에, 50 이상이면 뒤에 배치
	stable_partition(v.begin(), v.end(), Calculate);

	for (int& a : v)
	{
						  // 기존 순서 반영 
		cout << a << " "; // 30 10 20 70 80 60 
	}
}


📌 random_shuffle()

✅ random_shuffle(반복자 구간);

반복자 구간 내의 원소의 순서를 랜덤으로 뒤섞는다.

기본 랜덤기의 시작값이 srand(1)이기 때문에, 랜덤으로 섞고 싶다면 srand()를 사용하여 바꿔줘야한다.

  • srand : 랜덤 숫자 생성기의 시드(seed)를 설정하는 함수
    ➡ rand() 함수가 만들어내는 난수 시작점을 설정하는 함수
    ➡ 시드를 바꾸지 않으면 항상 같은 "랜덤" 값이 나온다.

  • srand((unsigned)time(NULL));
    ➡ 현재 시간이기 때문에 매 초마다 값이 바뀐다. 이 값을 시드로 사용하는 것.
    ➡ 따라서 매번 실행할 때마다 다른 랜덤 값이 적용된다.

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	// 처음 상태
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 30 40 50
	}

	srand((unsigned)time(NULL));

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

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 무작위 순서
	}
}


📌 reverse()

✅ reverse(반복자 구간);

구간내의 원소를 뒤집는다.

10 20 30 40 50 ➡ 50 40 30 20 10

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	// 처음 상태
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 30 40 50
	}

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

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 50 40 30 20 10
	}
}

✅ 반환 예시

reverse()는 반환값이 없기 때문에 만약 return vector<int>solution을 반환해야 한다면, 컨테이너 째로 반환해야한다.

vector<int> solution(vector<int> num_list) 
{
    reverse(num_list.begin(), num_list.end());
	
    return num_list;
}

✅ reverse_copy(1구간 반복자, 2구간 시작 반복자);

구간내의 원소를 뒤집은 후 다른 컨테이너에 저장한다.
➡ 값을 덮어씌우는 방식이기 때문에 목적지 순차열의 크기 >= 원본크기여야한다.

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	vector<int> v2 (10); // 사이즈 10

	reverse_copy(v.begin(), v.end(), v2.begin());

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // 50 40 30 20 10 0 0 0 0 0
	}
}

📌 rotate()

✅ rotate(시작 반복자, 원하는 반복자, 끝 반복자);

구간내의 원소를 왼쪽으로 원하는 만큼 이동시킨다.
이동하는 크기 : 원하는 반복자 - 시작 반복자

⭐ 쉽게 생각하면, 원하는 반복자는 [0]에 오고 싶은 원소를 가리키는 반복자!!!!!!!!⭐
➡ 아래의 코드에서 원하는 반복자는 v.begin() + 4
➡ v.begin() + 4 위치에 있는 원소 50이 [0]의 위치에 도달하기 위해 이동해야 하는 횟수 4번
➡❗ 즉, 4번 왼쪽으로 이동한 것이다!❗

int main()
{
	vector<int> v;

	v.push_back(10); // <- v.begin()
	v.push_back(20);
	v.push_back(30); 
	v.push_back(40); 
	v.push_back(50); // <- v.begin() + 4

	rotate(v.begin(), v.begin() + 4, v.end());

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 50 10 20 30 40
	}
}

✅ rotate_copy(1구간 시작 반복자, 원하는 반복자, 1구간 끝 반복자, 2구간 시작 반복자);

이동된 후 순차열을 다른 컨테이너에 저장한다.

int main()
{
	vector<int> v;

	v.push_back(10); // <- v.begin()
	v.push_back(20);
	v.push_back(30); // <- v.begin() + 2
	v.push_back(40);
	v.push_back(50);

	vector<int> v2(10); // 사이즈 10

	rotate_copy(v.begin(), v.begin() + 2, v.end(), v2.begin());

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // 30 40 50 10 20 0 0 0 0 0
	}
}

profile
치치
뉴비 개발자
이전 포스트

[STL] Algorithm - 제거 알고리즘

다음 포스트

[STL] Algorithm - 정렬 알고리즘

0개의 댓글