DFS로 순열 및 조합 구현

문제를 풀다보니 순열,조합을 구현해야하는 상황이 생겼다.

저번에는 이차원 배열 인덱스를 쫙펴서 X좌표는 몫 , Y좌표는 나머지로 3중 for문을 돌려 해결했지만, 그렇게 하면 시간복잡도가 터져버릴 거같다;; 그래서 찾아보니 c++에는 순열 라이브러리가 존재한다. 

 

1. STL 사용 

 next_permutation(v.begin() , v.end())

 

라이브러리를 쓸 수 없는 상황이 생긴다고 해서 dfs로 순열 및 조합 구현하는 방법을 좀 익혀두려고 한다. 

구글링을 해봤더니 보통 다 바로바로 print하는 코드들만 있는데, 사실 문제를 풀면서 순열을 출력할 상황은 많지 않다;;

그래서 배열에 저장하는 방식으로 코드를 짰다. 물론 구글링과 함께 ㅎ 

 

조합과 순열의 차이는 순서가 있다는 거다. 

보통 조합을 나열할 떄 오름차순으로 늘어놓는데, 이걸 포인트로 조합과 순열구현의 차이점이 생긴다. 

조합은 한 번 지나간 수에 대해선 다시 돌아오지않지만 순열은 다시 돌아온다. 

 

2. DFS 로 구현 

1) 조합 

앞에서 나온 숫자보다 작거나 같은 숫자는 생각하지 않는다. 오로지 더! 큰! 숫자만 생각해주는거다. 

그렇기 때문에 시작인덱스가 존재해 점점 커진다. 앞자리수와 뒤자리 수 사이에 대소관계가 있다고 생각하면 편하다.

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

int n, r;
vector<vector<int>> comb_arr;
vector<int> temp;
vector<bool> visited;

void combination(int idx, int cnt) {
	if (cnt == r) {
		comb_arr.push_back(temp);
		return;
	}
	for (int i = idx; i <= n; i++) {
		if (visited[i]) continue; 
		visited[i] = true;
		temp.push_back(i);
		combination(i, cnt + 1);
        // i를 넘겨주면 어차피 continue로 넘어간다 i+1을 사용해도 된다.
		temp.pop_back();
		visited[i] = false;
	}
}

int main()
{
	scanf("%d %d", &n, &r);
	visited.resize(n + 1);

	combination(1, 0);
	for (int i = 0; i < comb_arr.size(); i++) {
		for (int j = 0; j < comb_arr[i].size(); j++) printf("%d", comb_arr[i][j]);
		printf("\n");
	}
}

 

설명이 기가 막히게 잘 되어있다. 

yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

2) 순열 

[1,2,3,4] , [2,4,1,3] 앞자리 수와 뒤자리 수 사이에 대소관계가 없다.

순열과의 차이점은 딱하나 permute라는 함수에 시작인덱스를 인자로 주지 않는다. 

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

int n, r;
vector<vector<int>> perm_arr;
vector<int> temp;
vector<bool> visited;

void permute(int cnt) { 
	if (cnt == r) {
		perm_arr.push_back(temp);
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue; 
		visited[i] = true;
		temp.push_back(i);
		permute(cnt + 1);
		temp.pop_back();
		visited[i] = false;
	}
}

int main()
{
	scanf("%d %d", &n, &r);
	visited.resize(n + 1);
	permute(0);
	for (int i = 0; i < perm_arr.size(); i++) {
		for (int j = 0; j < perm_arr[i].size(); j++) printf("%d", perm_arr[i][j]);
		printf("\n");
	}
}

yabmoons.tistory.com/100?category=838490

[ 순열과 조합 구현 ] - 재귀를 통한 구현(2 - 순열) (C++)