next_permutation 순열 조합

 

순열 ( next_permutation )

 

C++에서는 algorithm 헤더에 있는 next_permutation을 사용하면 쉽게 순열을 구할 수 있다. 

파라미터로 순열을 구할 컨테이너의 시작과 끝 iterator를 인자로 받는다. 

bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
// custom
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp)

 

 

next_permutation을 사용할 때 주의할 점 

1. 오름차순으로 정렬된 값이어야 한다.

2. default로 operator < 를 사용해서 순열을 생성한다. -> 오름차순으로 순열을 생성한다.

 

사용 방법

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

using namespace std;

int alphabet[26];

int main() {
	vector<int> v = {1,1,2,3,4,5};
	do {
		for(auto i: v)cout << i <<' ';
		cout << '\n';
	} while (next_permutation(v.begin(),v.end()));
}

 

위 처럼 do{}while();을 사용해주면 된다.

 

참고로 next_permutation의 시간복잡도는 

최악의 경우! 하나의 순열을 생성하는 데 O(N)

모든 순열을 생성하는 데는 O(N!*N)이 걸린다. 다만, 중복을 구할때는 조금 다른데 이 경우는 next_permutatioin을 이용한 조합을 하면서 계산해 보기로!! 

 

조합

 

조합 같은 경우에는 나는 통상 void combination() 함수를 따로 만들어서 DFS? 재귀? 의 방식으로 구현해줬다. 

예를 들자면 아래와 같다.

int combination(vector<int> &team, int num, int k) {
	if (num > N) {
		v.push_back(team);
		return 0;
	}

	team[num]=1;
	combination(team, num + 1, k+1);
	team[num]=0;
	combination(team, num + 1, k);

	return 0;
}

 

 

여기서, 나는 team[num] = 1, 0 을 넣어서 나중에 판별해줬는데 이건 입력된 배열에서 모든 idx를 포함해줘야 했고, 

고른 것을 제외한 나머지와 비교해줘야 했기 때문이다. 

 

근데, next_permutation을 사용해서도 위 처럼 조합을 구해줄 수 있다. 

 

사용 방법

ex) 2개의 원소를 고르는 모든 경우의 수 

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

using namespace std;

int alphabet[26];

int main() {
	vector<int> v{1,1,2,3,4,5};
	// vector<int> v = {1,1,2,3,4,5};
	vector<int> temp{ 1,1,0,0,0,0 };

	do {
		for (int i = 0; i < v.size(); i++) {
			if (temp[i] == 1)
				cout << v[i] << ' ';
		}
		cout << '\n';
	} while (next_permutation(v.begin(),v.end()));
}

 

이렇게 구해줄 수 있다.

 

시간 복잡도를 계산해보면 최악의 경우!

O(6 * 6 / 2!4!)이렇게 된다.

O(N)은 한 순열을 만드는데 걸리는 시간이라고 했다. 

그리고 중복된 수를 포함한 수열은 N!/(중복된 수)! 의 경우의 수를 가진다. 

위의 경우에는 1이 두개 0이 네개로 N!/(4!2!)를 갖게 된다는 것이다. 

 

 

GPT가 그렇다고...

 

 

next_permutation 구현해보기. (밤에..)

그럼 어떤식으로 돌아가는지 궁금하기 때문에 next_permutation을 직접 구현해보겠다 ^_^

https://hanil0623.tistory.com/2

[C++ STL] next_permutation의 내부 구현 방법

 

next_permutation은 간단하게

특정한 수열의 가능한 배열 중에 입력으로 들어온 수열을 사전순으로 마지막이 될 때까지 순회시켜 마지막이면 false를 리턴하고 사전순 가장 처음인 순서대로 주어진 수열을 만들어 놓는다

 

고 한다. 그럼, 어떻게 주어진 수열이 사전순 마지막인지 평가하는가??

=> 내림차순으로 정렬되어 있는지 알아본다. A[K] >= A[K+1]

 

*A[k] < A[k+1]이 성립하는 k가 있으면 오름차순을 꺠는 것으로 A[k]부터 수열 끝까지에 있는 수들의 순서를 조작함으로 사전순으로 뒤에 있는 순열들을 만들어 낼 수 있다고 한다.

 

1. 오름차순으로 정렬된 본래의 순열부터 출발
2. 그 다음 수열로 넘어갈 때는, 다음 수와 오름차순 관계를 이루는 가장 뒤에 있는 수들 한 쌍을 찾아서, 즉 앞서 간단히 말했던 A[k] < A[k+1]이 성립하는 가장 큰 k를 찾는다.
3. k보다 인덱스가 큰 수들 중에서, A[k]보다 큰 수를 찾고(이를 A[h]라 한다.)
4. A[k]와 A[h]를 바꾼다
5. A[k+1]부터 끝까지 부분 수열을 오름차순으로 정렬.

 

 

 

1,2,3,4의 next_permutation을 잘 보면, 3<->4 (가장 큰 k = 3)

1,2,4,3에서 2<->4 (가장 큰 k=2)

 

이런식으로 흘러가는 걸 잘 볼 수 있다.

 

#include<iostream>
#include<iterator>
#include<algorithm>

using namespace std;

int arr[] = { 1,2,3,4 };

template <class BidirectionalIterator>
bool next_permutation1(BidirectionalIterator* first, BidirectionalIterator* last) {
	if (first == last) return false; //원소가 하나도 없다.
	//[)
	BidirectionalIterator* i = last;

	//시작과 끝이 같다 => 한칸짜리 순열이다.
	if (first == --i) return false;

	for (;;) {
		BidirectionalIterator *i1, *i2;
		i1 = i;
		// --i는 이전 것 i는 현재의 것.
		if (*--i < *i1) { // 오름차순이면?
			i2 = last;
			while (!(*i < *--i2));//끝에서부터 A[k]<A[h]를 만족하는 h 탐색
			std::iter_swap(i, i2);
			std::reverse(i1, last); // 내림차순을 정렬된 부분 수열을 오름차순으로 만들어준다.
			return true;
		}
		//완전 내림 차순
		if (i == first) {
			std::reverse(first, last);
			return false; // 더이상 없다.
		}
	}
}

int main() {
	do {
		for (int i = 0;i < 4;i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
	}while(next_permutation1(arr, arr + 4));
}

 

 

[++개인 후기]

얼마 전에 PCCP 시험을 쳤는데, 문제 자체는 그렇게 안 어려웠는데 시간이 부족해서 4번 문제를 못풀었다. 

4번 문제를 시작할 때 40분 정도 남아있었고 문제를 보면서 아이디어 구상, 구현까지 하기에 시간이 좀 모자랐다. 

물론, 4번을 좀 더 빠르게 생각해냈으면 풀 수 있었겠지만... 제일 어려운 4번을 구현하다말고 시간이 부족했던 걸로 보면 1,2,3번에서 시간을 줄여야할 필요성도 느꼈다. 

 

게다가 내가 생각하는 내 문제점이 하나 있는데 C++ 문법에 대해 안 익숙하다는 것이다. 

외울 것도 외워야 하고 이게 되던가..? 하는 부분이 많아서 구현할 때 조금씩 시간이 늘어난다. 그냥 문제를 풀 땐 상관없지만 실전 코테에서는 이런 시간도 줄여야 하니까 앞으로 기본부터 하나씩 정리해볼 생각이다. ( 실버 문제부터 풀어보자!)

 

+ do while 뒤에는 ;를 붙이는 걸 잊지말자.

 

https://velog.io/@kasterra/nextpermutation-%EC%9D%98-%EA%B5%AC%ED%98%84

next_permutation 의 구현