되도록 심플하게 글을 작성하려합니다.
순열 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다
permutation 알고리즘은 c++ 에선 여러가지 방법중 2가지를 알려드리려합니다.
하나는 재귀함수(backtracking)을이용한 직접 구현과, 라이브러리를 이용한 next_permutation을 이용
재귀함수를 이용한 소스코드 :
#include<bits/stdc++.h>
using namespace std;
vector<int> p, check;
int n;
void backtrack(int h = 0) {
if (h >= n) {
for (int i : p)
cout << i << " ";
cout << "\n";
return;
}
for (int i = 0; i < n; i++) {
if (check[i] == 0) {
check[i] = 1;
p[h] = i;
backtrack(h + 1);
check[i] = 0;
}
}
}
int main()
{
n = 3;
check = p = vector<int>(n);
backtrack();
}재귀를 이용한코드는 check 방문배열이 하나더 필요하다는것
라이브러리를 이용한 소스코드 :
#include<bits/stdc++.h>
using namespace std;
vector<int>p;
int n;
int main()
{
n = 3;
p = vector<int>{ 0,1,2 };
sort(p.begin(), p.end());// 정렬이 되어있어 이코드는 필요가 사실상없음 그러나 정렬이 되어야 한다는것을 알아야함
do {
for (int i = 0; i < n; i++)cout << p[i] << " ";
cout << "\n";
} while (next_permutation(p.begin(), p.end()));
}
라이브러리를 이용하면 반드시 정렬이 필요하다 정렬이 되어있을경우 정렬 코드를 넣지않아도 되지만
종종 잊어버리고 왜안되지? 하는경우도 있으니 정렬을 넣어주는 습관을 들이도록 하자
두코드 비교하면 라이브러리를 사용하는것이 더 깔끔하다 그러나. 라이브러리를 사용하는 코드는
사실 그리 빠르지않다 n= 10일경우 10! 일경우
시간을 비교해 드리면
10!을 만들어내는 코드만 시간측정한후의 결과이다.
보시다시피 재귀함수는 0.7초내에 끝났지만
라이브러리는 3초나 걸렸다. 컴퓨터 사양마다 차이는있겠지만
코딩테스트에서 10!까지는 라이브러리를 작성해도 대체로 괜찮았습니다.
n이 짧은경우 라이브러리가 빠르게 코딩을 할수있지만 재귀함수보다는 조금 느리다는점을 유의해두시길
조합 : 서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합이라고 한다. 이 조합의 총수는 nCr로 표시하는데 이 기호는 combination(조합)의 머리글자에서 따온 것이다. nCr의 계산은
[네이버 지식백과] 조합 (두산백과 두피디아, 두산백과)
이또한 재귀함수와 라이브러리를 이용한 코드를 보여드리려합니다.
재귀함수를 이용한 소스코드 :
#include<bits/stdc++.h>
using namespace std;
vector<int> p,check;
int n,r;
void backtrack(int h=0){
if(h>=r){
for(int i:p)cout<<i<<" ";
cout<<"\n";
return;
}
for(int i=0;i<n;i++){
if(check[i]==0){
if(h-1>=0&&p[h-1]>i)continue;//반복수를 제거
check[i]=1;
p[h]=i;
backtrack(h+1);
check[i]=0;
}
}
}
int main()
{
n=4;
r=2;
check=vector<int>(n);//n개중
p=vector<int>(r);//r개를 뽑아야하니 r개의 사이즈
backtrack();
}n개중 r개를 뽑아야하니 탐색깊이를 r개까지만 하면되고 반복수를 제거하기위해 if문을 추가만해주면 조합코드가
완성됩니다. 순열코드랑 매우 비슷하죠??
라이브러리를 이용한 소스코드 :
#include<bits/stdc++.h>
using namespace std;
vector<int>p;
int n;
int main()
{
n = 5;
int r = 3;
vector<int>p(r); //n개중 r개를 0으로 집어넣고
for (int i = r; i < n; i++) p.push_back(1); //나머지 n-r개를 1로집어넣음
sort(p.begin(), p.end()); //정렬이 되어있어 필요없지만 습관화 하셈
do {
for (int i = 0; i < n; i++) {
if (p[i] == 0)
cout << i << " ";
}
cout << endl;
} while (next_permutation(p.begin(), p.end()));
}
라이브러리를 이용한 코드는 한가지를 고려해야합니다.
p배열을 n개중 r개를 선택했을때 r을 0으로잡을지 1로 잡을지 저같은경우는 r을 0으로 선택합니다.
이유는 미리 0으로 넣은후 나머지 n-r개를 1로 넣게되면 sort를 할필요가 없으니까요 sort코드를 넣긴했지만
next_permutation을 이용하기위해선 정렬되어있어야한다는것을 강조하기위해서 넣은거지 제코드에선 무의미한코드입니다.
선택은 프로그램 작성자가 스스로 해야하는겁니다.
당연한 얘기겠지만 재귀함수로 이용한 코드가 더빠릅니다.
그러나 편의성을위해선 라이브러리도 빠르게 코딩을 할수있습니다.