[순열] 순열 구현하기 C++

알고리즘 문제를 해결하다보면 순열과 조합을 이용해야하는 일이 빈번히 발생한다.

순열을 구현하는 방법 중 하나인 원소의 방문을 체크해 가며 구현하는 방법과 STL을 이용하는 방법을 소개하겠다.

 

 

1. 재귀를 이용한 순열 구현

 

다음 방법은 크기가 3인 모든 수열을 출력하는 방법이다.  

checked배열로 현재 vector에 들어있는 값들을 확인하고, 순열에 아직 포함되지 않은 원소를 선택하여 vector에 넣어주는 방식으로 구현하였다. 

또한 vector에 필요한 크기의 원소가 모두 들어가면 출력하는 방법으로 순열을 구할 수 있다. 

//순열구현하기
#include <iostream>
#include <vector>
using namespace std;
int arr[5];
bool checked[5];
vector<int> v;
void Input() {
	arr[0] = 1;
	arr[1] = 2;
	arr[2] = 3;
	arr[3] = 4;
	arr[4] = 5;
}

void DFS(int cnt) {

	if(cnt == 3) {
		for (int i = 0; i < 3; i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	}

	for (int i = 0; i < 5; i++) {
		if (checked[i] == true) continue;
		checked[i] = true;
		v.push_back(arr[i]);
		DFS(cnt + 1);
		v.pop_back();
		checked[i] = false;
	
	
	}



}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	Input();
	DFS(0);

}

 

 

 

2. STL을 활용한 방법

next_permutation함수를 사용하면 굉장히 쉬운 방법으로 순열을 찾을 수 있습니다. 

하지만 해당 함수를 사용하기 위해서는 원소들의 오름차순 정렬이 필수입니다. 

//순열구현하기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[5];
bool checked[5];
vector<int> elements{1,2,3,4,5};



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	sort(elements.begin(), elements.end());

	do {
		for (auto it = elements.begin(); it != elements.end(); it++) {
			cout << *it << " ";
		
		}
		cout << "\n";

	
	} while (next_permutation(elements.begin(), elements.end()));

}

 

* next_permutation을 활용하여 조합을 구현할 수도 있습니다. 

바로 조합의 크기 만큼의 1과 나머지 크기를 0으로 채워준 vector를 선언해주면, 0과 1을 활용하여 조합을 만들 수 있습니다. 

 

만일 3개의 원소 중 1개의 원소로 조합을 만든다고 가정해 봅시다.

{0,0,1}과 같이 새로운 vector를 만듭니다.(이 역시 정렬이 필수입니다!)

 

해당 원소들을 next_permutation()을 활용해 돌리게 되면

{0,0,1}, {0,1,0}, {1,0,0}...과 같이 조합을 만들 수 있습니다. 

그리고 1인 부분의 원소를 출력하게되면 조합을 출력하게 됩니다.