[C++] 백트래킹, 순열, 조합, 부분집합, 중복순열, next_permutation

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

- 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘
- 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제
- 모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것
- 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음
- 만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감

 

‼️ 주의

재귀로 푸니까 스택 메모리 제한을 확인해야된다.
N이 클 경우 백트래킹을 적용하면 시간초과 난다.

 

백트래킹 알고리즘의 시간 복잡도는 주로 문제의 조건에 따라 달라진다.

선택할 수 있는 숫자가 N개이고, 수열의 길이가 M이므로 총 경우의 수는 O(N^M)다. 

따라서 최악의 경우에는 지수 시간이 소요될 수 있다.

백트래킹 코드는 이 틀 내에서 문제에 따라 적절히 응용해야함 (조합 코드)
인덱스 설정이나 탈출 조건은 문제에 따라 바꿔주면 되고

⭐ 상태변화 & 원상복구가 중요함 원래대로 복구하는거 빼먹지 않도록 주의

void backtracking(int cnt, int idx) {
	if (cnt == m) {
		//조건 만족시 해야될 일 적음
		return;
	}
	for (int i = idx; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true; //상태변화
			backtracking(cnt + 1, i+1); 
			visited[i] = false; //원상복구
		}
	}
}

 

 

next_permutation

순열과 조합을 가지고 빡센 문제가 많은데 이런 문제들을 백트래킹으로 해결할 수 있지만 아무래도 백트래킹은 실수할 수 있는 여지가 있고 코드가 길어진다. 그런데 이 next_permutation함수만 있다면 아주 깔끔하게 순열과 조합을 해결 할 수 있다.

 

현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다.

다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.

 

함수를 실행하기 전,  무조건 오름차순 정렬이 되어있어야 한다.

 

ex) 순열을 구하고 싶은 1-2-3-4의 배열이 있다고 가정을 하면

next_permutation의 함수를 사용하면 배열의 값들이 다음 순열인 1-2-4-3로 바뀌고 함수는 true를 반환한다.

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

1 2 3 4
1 2 4 3
1 3 2 4

...

4 2 3 1
4 3 1 2
4 3 2 1

 

prev_permutation

next_permutation과 거의 동일한데 다음 순열 대신 이전 순열을 구해준다는 것만 다른 함수입니다.

현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 

이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

 

함수를 실행하기 전, 무조건 내림차순 정렬이 되어있어야 한다.

 

ex) 순열을 구하고 싶은 4-3-2-1의 배열이 있다고 가정을 하면 prev_permutation의 함수를 사용하면 배열의 값들이 다음 순열인 4-3-1-2로 바뀌고 함수는 true를 반환한다.

int main() {
	string s = "dcba";
	do cout << s << '\n';
	while (prev_permutation(s.begin(), s.end()));
}

4 3 2 1
4 3 1 2
4 2 3 1

...

1 3 2 4
1 2 4 3
1 2 3 4

 

 

Combination

함수의 이름에서 볼 수 있듯 이 함수를 가지고 순열(permutation)을 잘 처리할 수 있는데

만약 조합(combination)이 필요하다면 어떻게 해야할까?

int main() {
	vector<int> P{ 1, 2, 3, 4 };
	vector<int> v{ 1, 1, 1 ,0 };
	do {
		for (int i = 0; i < 4; i++) if (v[i]) cout << P[i] << ' ';
		cout << '\n';
	} while (prev_permutation(v.begin(), v.end()));
}

 

combination은 순서에 상관없이 수를 선택하는 것을 의미하며

여기선 선택하는 수의 개수 k가 고정일 때(=nCk)를 생각해보자.

 

예를 들어 P = { 1, 2, 3, 4 }, k = 3이라면 3개를 순서 없이 뽑는 모든 경우

(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4) 이렇게 4개의 조합이 가능하다.

0과 1을 이용해서 next_permutation을 돌리는 방법으로 해결한다. 

5개에서 3개를 뽑는 문제라면 배열 a를 {0,0,0,1,1}로 두면 된다.

이건 v = { 0, 1, 1, 1 }과 같이 뒤쪽 k개의 원소를 1로 채운 순열을 만들어서

next_permutation을 사용하면 처리할 수 있다. 

즉, v에 대한 permutation을 순회하며 v[i] = 1인 P[i]만 골라서 조합을 만들어주면 된다.
(next_permutation은 중복이 있는 순열에서도 잘 작동하며, 전체 연산량의 합은 중복이 없을 때보다 적다)

만약 combination을 사전순으로 순회하고 싶다면 v = { 1, 1, 1, 0 }에서 시작해서 

prev_permutation을 돌리거나 0, 1을 뒤집어서 { 0, 0, 0, 1 }부터 next_permutation을 돌려주면 된다.

 

 

문제 풀이는 어떤걸로?

단순 순열, 조합을 필요로 하면서 효율성을 고려하지 않아도 되는 문제라면 next_permutation을 사용하고,

중복 순열, 중복 조합 등을 필요로 하거나 시간 최적화가 필요한 문제는 백트래킹으로 처리한다.