지나공 : 지식을 나누는 공간

C++ 같은 것이 있는 순열과 조합 : dfs(백트래킹), next_permutation으로 구현, 차이, 중복순열 중복조합 등 본문

Algorithm/C++ 노트

C++ 같은 것이 있는 순열과 조합 : dfs(백트래킹), next_permutation으로 구현, 차이, 중복순열 중복조합 등

해리리_ 2021. 2. 4. 15:57

코드 순서는,

 

  • dfs 백트래킹 순열
    • 일반 순열 (주어진 원소를 모두 나열)
    • 주어진 원소 중 원하는 개수를 뽑아서 순열
    • 주어진 원소에 일부 중복된 원소가 있을 때
      • 중복 허용하기
      • 중복 제거하기 (같은 것이 있는 순열)
  • next_permutation 순열
    • 일반 순열 (주어진 원소를 모두 나열)
    • 주어진 원소 중 원하는 개수를 뽑아서 순열
    • 주어진 원소에 일부 중복된 원소가 있을 때
      • 중복 허용하기
      • 중복 제거하기 (같은 것이 있는 순열)
  • dfs 백트래킹 조합
    • 중복된 원소가 없는 조합
  • next_permutation 조합
    • 중복된 원소가 없는 조합
  • 중복순열과 중복조합 구현하기

 

dfs 백트래킹 순열

 

- 일반 순열 (주어진 원소를 모두 나열)

 

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

vector<char>v; //순열을 구해야 할 주어진 원소
vector<char> result; //완성된 순열이 저장되고 갱신되는 공간
int m; //순열에 들어가는 원소의 수
bool visit[4]; // 문자 4개의 방문여부 체크 
void dfs() {
	if (result.size() == m) {
		for (char i : result) {
			cout << i << " ";
		}
		cout << endl;
        return;
	}
	for (int i = 0; i < v.size(); i++) {
		if (!visit[i]) {
			visit[i] = true;
			result.push_back(v[i]);
			dfs();
			result.pop_back();
			visit[i] = false;
		}
	}
}
int main() {
	m = 4;
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');
	dfs();
	return 0;
}

 

abcd 네 원소에 대한 순열 : 24가지 출력

 

- 주어진 원소 중 원하는 개수만 뽑아서 순열

 

동일한 코드에서 m 값만 변경하면 된다.

아래는 m을 3으로 해서 abcd 네 원소 중 3개 원소를 선택하여 그 순열을 구한 모습이다.

그러면 4개 중에 3개를 뽑는 경우의 수 4C3, 뽑힌 3개의 원소에 대한 순열 경우의 수 3!을 해서 4C3 * 3! = 24가지다.

 

a b c 네 원소 중 3개를 뽑아서 나열 : 24가지 출력

 

 

-  주어진 원소에 중복된 원소가 있을 때 : 중복 허용하기

 

주어진 원소가 a b b c 로 중복되는 원소가 있다고 하자.

위의 백트래킹 순열 구하는 코드를 그대로 적용해서 원소만 변경해주면 아래와 같은 결과가 나온다. 

 

똑같이 24가지가 나오는데 자세히 보면 순열이 중복된다.

예를 들어 a b b c 가 여러 번 나온다.

 

같은 것이 있는 순열인데 중복 제거를 안한 상태 : 24개

 

- 주어진 원소에 중복된 원소가 있을 때  : 중복 제거하기

 

그럼 이 중복을 제거해보자. 주의할 게 중복순열 개념과는 다르다.

 

중복 순열은 abcd 4개원소를 중복을 허용해서 나열하는 것이므로 24가지보다 경우가 많다. 한 자리마다 올 수 있는 경우의 수가 4가지 이므로 만약 4개 원소를 나열한다고 하면 4 * 4 * 4 * 4이다. (중복 순열 구현은 아래에 적겠다.)

 

반면 현 상황은 같은 것이 있는 순열로, 중복 순열은 아닌데 순열을 구했더니 일부 중복된 원소 때문에 같은 순열 결과가 여러번 나오는 것이다. 이제 이 같은 결과로 나오는 순열들은 빼고 개수를 세고 싶다.

 

고등학교 때인가? '같은 것이 있는 순열'이라는 유형으로 문제를 푼 적이 있을 것이다.

 

그때 어떻게 했었냐 하면, a a b c d e e e 로 8개 원소라고 할 때 아래와 같이 계산한다.

 

일반적인 8개 원소의 순열 개수인 8!을, a가 2번 중복되니까 2!으로 나누고 e가 3번 중복되니까 3!으로 나눈다.

 

이걸 코드로 구현해보겠다. a b b c d d 로 구현해보겠다.

 

일단 쓰인 알파벳이 a b c d 까지만 쓰인다고 가정하면 배열을 선언해서 해당 알파벳이 쓰인 개수를 셀 수 있다.

이건 순열 결과를 출력하지 않고 중복 제거한 개수만 세겠다.

 

 

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

vector<char>v; //순열을 구해야 할 주어진 원소
vector<char>result; //순열 결과가 들어갈 벡터
int m; //순열에 들어가는 원소의 수
bool visit[6]; // 문자 6개의 방문여부 체크 
int alpha[4]; //알파벳 중복체크
int ans; //순열의 개수

int fact(int n) {
	int res = 1;
	while (n > 0) {
		res = res * n;
		n--;
	}
	return res;
}

void dfs() {
	if (result.size() == m) {
		ans++;
        return;
	}
	for (int i = 0; i < v.size(); i++) {
		if (!visit[i]) {
			visit[i] = true;
			result.push_back(v[i]);
			dfs();
			result.pop_back();
			visit[i] = false;
		}
	}
}
int main() {
	m = 6;
	v.push_back('a');
	v.push_back('b');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');
	v.push_back('d');

	//알파벳 개수 세기
	for (int i = 0; i < v.size(); i++) {
		alpha[v[i] - 'a']++;
	}
	dfs();
	cout << "중복 제거 전 순열 개수 : " << ans << endl;
	for (int i = 0; i < sizeof(alpha)/4; i++) {
		if (alpha[i] > 1) { //중복되는 원소라면
			ans = ans / fact(alpha[i]);
		}
	}
	cout << "중복 제거 후 순열 개수 : " << ans << endl;
	return 0;
}

 

실제로 계산해보면 맞게 나온 것이다.

계산하면 180이다.

 

관련 문제로는 백준 애너그램이 있다.

next_permutation 순열

- 일반 순열

 

next_permutation은 algorithm 헤더에 있다. 시간복잡도는 O(N)이다.

 

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

vector<char>v; //순열을 구해야 할 주어진 원소

int main() {
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');

	do {
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << endl;
	} while (next_permutation(v.begin(), v.end()));

	return 0;
}

24개 순열이 정렬되어 나온다.

 

- 주어진 원소 중 원하는 개수만 뽑아서 순열

 

next_permutation은 그냥 원하는 개수만 뽑는 조합의 코드를 작성하면 아래와 같은 결과가 나온다.

그리고나서 얘네를 하나씩.. 순열을 시키면 되겠으나. 굳이?인 것 같다. 이런 건 백트래킹 사용하는 게 좋겠다.

 

 

-  주어진 원소에 중복된 원소가 있을 때 : 중복 허용하기

next_permutation은 순열을 만들기 위한 알고리즘으로, 중복을 제거한 상태로 반환된다.

따라서 아래와 같이 a b b c d e 에 대해 그냥 일반적인 방식으로 next_permutation을 돌리면 알아서 720이 아니라 중복이 제거된 180개의 결과가 나온다.

 

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

vector<char>v; //순열을 구해야 할 주어진 원소
int ans; //순열에 들어가는 원소의 수

int tmp[4] = { 0, 1, 1, 1 };

int main() {
	v.push_back('a');
	v.push_back('b');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');
	v.push_back('d');

	do {
		ans++;
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << endl;
	} while (next_permutation(v.begin(), v.end()));
	cout << ans <<endl;
	return 0;
}

 

180가지의 경우의 수 출력

 

-  주어진 원소에 중복된 원소가 있을 때 : 중복 제거하기

 

위에서 말한 것과 같이 그냥 돌리면 알아서 중복 제거된 결과가 반환된다.

 

dfs 백트래킹 조합

 

- 중복된 원소가 없는 조합

일단 백트래킹에서의 조합은 순열과 되게 비슷하게 생겼지만 아주 큰 차이가 있다.

여기서의 포인트는, 이미 선택한 인덱스보다 앞의 인덱스는 쳐다보지 않는 것이다.

 

차이를 보기 위해 잠시 순열 코드와 조합 코드를 비교해보겠다. 

 

순열은 for문이 항상 i=0 부터다.

 

조합은 현재 인덱스를 받고 그 이후부터 for문이 돈다.

 

for문의 시작 값을 보면 알 수 있듯이, 순열은 항상 0부터, 조합은 현재의 idx 이후부터 재귀호출을 한다.

순열은 abc를 뽑았으면 acb, bac 등을 또 뽑아야 하고, 조합이면 abc를 뽑았으면 끝이다. 이미 뽑은 자리는 더이상 보지 않고 그 이후의 자리의 알파벳만 뽑는 것이다.

 

dfs 조합 코드.

 

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

vector<char>v; //조합을 구해야 할 주어진 원소
vector<char> result; //완성된 조합이 저장되고 갱신되는 공간
int m; //조합할 원소 수
bool visit[4]; // 문자 4개의 방문여부 체크 
void dfs(int idx) {
	if (result.size() == m) {
		for (char i : result) {
			cout << i << " ";
		}
		cout << endl;
        return;
	}
	for (int i = idx; i < v.size(); i++) {
		if (!visit[i]) {
			visit[i] = true;
			result.push_back(v[i]);
			dfs(i+1);
			result.pop_back();
			visit[i] = false;
		}
	}
}
int main() {
	m = 2;
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');
	dfs(0);
	return 0;
}

 

결과는 4C2이다.

 

- next_permutation 조합 구현

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

vector<char>v; //순열을 구해야 할 주어진 원소
int tmp[4] = { 0, 0, 1, 1 };

int main() {
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');

	do {
		for (int i = 0; i < 4; i++) {
			if (tmp[i] == 1) {
				cout << v[i] << " ";
			}
		}
		cout << endl;
	} while (next_permutation(tmp, tmp+4));

	return 0;
}

 

결과

중복순열과 중복조합

 

중복순열

 

이건 너무 간단하다. 주어진 원소가 3개이고 나열하려는 원소 수가 3개라면 한 자리에 올 수 있는 경우의 수가 3이므로 3*3*3이다.

 

코드 구현에서 볼 점은 dfs의 두 번째 for문에 있는 result[cnt] = v[i]이다. result의 값을 계속해서 변경해준다.

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

vector<char>v; //순열을 구해야 할 주어진 원소
char result[3]; //완성된 순열이 저장되고 갱신되는 공간

void dfs(int cnt) {
	if (cnt == 3) {
		for (int i = 0; i < 3; i++) {
			cout << result[i] << " ";
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < v.size(); i++) {
		//배열을 만들어서 계속 값을 바꿈.
		result[cnt] = v[i];
		dfs(cnt + 1);
	}
}
int main() {
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	dfs(0);
	return 0;
}

 

 

중복조합

 

3개 원소 a,b,c 중 중복을 허용해서 4개를 뽑는 방법을 코드로 작성했다. 아래 식처럼 개수는 15개가 나올 것이다.

조합 구하는 것과 비슷하게 for문이 idx부터 시작되는데 중복이 들어갔으므로 result[i] = v[i] 이런 식으로 방문체크 없이 중복 허용 조합을 구할 수 있다.

 

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

vector<char>v; //조합을 구해야 할 주어진 원소
char result[3]; //완성된 조합이 저장되고 갱신되는 공간
int ans;
void dfs(int idx, int cnt) {
	if (cnt == 4) {
		for (int i = 0; i < 3; i++) {
			cout << result[i] << " ";
		}
		cout << endl;
		ans++;
		return;
	}
	for (int i = idx; i < v.size(); i++) {
		//배열을 만들어서 계속 값을 바꿈.
		result[cnt] = v[i];
		dfs(i, cnt + 1);
	}
}
int main() {
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	dfs(0, 0);
	cout << ans;
	return 0;
}

 

 

728x90
저작자표시

'Algorithm > C++ 노트' 카테고리의 다른 글

C++ 한번에 한줄로 입력받기, 글자 수 왜 다른가  (0) 2021.01.06
C++로 정렬 알고리즘 sort 사용법, 내림차순, 특정 변수 기준 정렬(연산자 오버로딩, compare 함수 활용)  (1) 2020.12.30
[C++] string에서 특정원소의 위치 찾기 - find()  (0) 2020.08.11
hash_map | unordered_map | map 차이 비교, 특징 정리 - C++  (0) 2020.07.07
STL 정리 - 개념과 컨테이너 종류  (0) 2020.07.07
'Algorithm/C++ 노트' Related Articles more
Comments