[코딩 테스트 준비 - 기초] 6. 브루트 포스 - 순열

1. 다음(이전) 순열 구하기

• 순열은 순서가 중요한 경우 사용한다.
• 순열을 사전순으로 나열했을 때, 첫 순열은 배열을 오름차순 정렬한 것이고, 마지막 순열은 내림자순 정렬한 것이다.
• 다음 순열이란 i번째 순열이 주어진 경우 i+1번째 순열을 의미한다. (이전 순열은 반대)
• 시간복잡도는 배열의 크기가 N인 경우 O(N * N!)이다. 따라서 N<=10인 경우 1초 내에 들어온다.

 

C++에서는 다음 순열(next_permutation)과 이전 순열(prev_permutation)을 구하는 STL이 있다. 

• algorithm 헤더에 있다.
• 다음(이전) 순열이 있는 경우 true를, 그렇지 않은 경우 false를 반환한다.
• 첫 번째 인자로 배열의 시작을, 두 번째 인자로 배열의 마지막을 넣어준다.
• 이를 이용해 모든 순열을 구하기 위해서는 정렬을 해줘야 한다.
  • 오름차순 정렬 -> 다음 순열 이용
  • 내림차순 정렬 -> 이전 순열 이용

 

[백준 10972 다음 순열 & 백준 10973 이전 순열] 

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

int main() {
	int n;
	cin>>n;

	int arr[n];
	for(int i=0; i<n; i++)
		cin>>arr[i];

	if(next_permutation(arr, arr + n)){ //이전 순열: prev_permutation 
		for(int i=0; i<n; i++)
			cout<<arr[i]<<" ";
	} else{
		cout<<-1;
	}
	cout<<'\n';

	return 0;
}

 

[백준 10974 모든 순열] 

• 첫 순열로 먼저 출력하고 다음 순열을 확인해야 하므로 do-while문을 사용한다.

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

int main() {
	int n;
	cin>>n;

	int arr[n];
	for(int i=1; i<=n; i++)
		arr[i-1] = i;

	do{
		for(int i=0; i<n; i++)
			cout<<arr[i]<<" ";
		cout<<'\n';
	} while(next_permutation(arr, arr + n));


	return 0;
}

 

cf) 직접 next_permutation 구현하기

#include <algorithm> //sort 때문에 필요

bool next_permutation(int* a, int n){
	//1. 무엇으로 시작하는 마지막 순열인지 찾기 (i 찾기)
	int i = n-1;
	while(i > 0 && a[i-1] >= a[i]) i--;

	if(i <= 0) return false; //마지막 순열인 경우

	//2. a[i-1]보다 크고 마지막 순열에 있는 수 중 가장 오른쪽에 있는 수 찾기 (j 찾기)
	int j = n - 1;
	while(j >= i && a[j] <= a[i-1]) j--;

	//3.swap
	swap(a[i-1], a[j]);

	//4. 마지막 순열 오름차순
	sort(a + i, a + n);
	return true;
}

 

 

2. 순열로 브루트 포스 풀기

STL을 사용하니까 확실히 편하긴 편하다.. 재귀로 구현할 때는 직관적이지 않아서 구현하는데 시간이 오래 걸렸는데 순열을 사용하니까 빨리 풀린다!

 

 

[백준 10819 차이를 최대로] - Bruteforce

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

int main() {
	int n;
	cin>>n;

	int arr[n];
	for(int i=0; i<n; i++)
		cin>>arr[i];

	sort(arr, arr + n);

	int ans = 0;
	do{
		int sum = 0;
		for(int i=0; i<n-1; i++){
			int sub = arr[i] - arr[i+1];
			if(sub < 0) sub = -sub;
			sum += sub;
		}
		ans = max(ans, sum);
	} while(next_permutation(arr, arr + n));

	cout<<ans<<'\n';

	return 0;
}

 

[백준 10971 외판원 순회2] - Backtracking

• 123, 231, 312는 모두 같은 결과를 내는 것임을 알아내면 시간복잡도를 줄일 수 있다.
• 출발지를 하나로 고정시켜 반복을 피하는 것이다.
• if(arr[0] != 0) break; 라는 조건을 걸면 된다.

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

int main() {
	int n;
	cin>>n;

	int w[n][n];
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin>>w[i][j];

	int arr[n]; //순서 저장
	for(int i=0; i<n; i++)
		arr[i] = i;

	int ans = 10000000;
	do {
		if(arr[0] != 0) break; //시작점을 0로 고정한 경우 나머지는 볼 필요X
    
		int cost = 0;
		bool flag = true;
		for(int i=0; i<n-1; i++){
			if(w[arr[i]][arr[i+1]] == 0){ //길이 없는 경우
				flag = false;
				break;
			}
			cost += w[arr[i]][arr[i+1]];
		}

		//처음 도시로 돌아옴
		int back = w[arr[n-1]][arr[0]];
		if(!back) flag = false;

		if(flag) ans = min(ans, cost + back);
	} while(next_permutation(arr, arr + n));

	cout<<ans<<'\n';

	return 0;
}