백준 알고리즘 기초 - 브루트 포스 (순열)

순서가 중요한 놈

 

자소서와 병행하느라 진도가 늦는 기분..

하지만 속도보다 중요한 건, 확실하게 알고 넘어가는 것!

초조해 하지말자.

정리 시작!

-

* 순열 : 임의의 수열을 다른 순서로 섞는 연산. 문제를 보면서 이해하자.

* 다음 순열(mid) : STL을 사용해도 되지만, 원리를 알기 위해 직접 구현 해보자.

10972번: 다음 순열

#include <iostream>
#include <algorithm>

using namespace std;

int p[10000];

bool next_permutation(int *a, int n) {
	int i = n - 1;
	while ( i > 0 && a[i] <= a[i - 1]) i -= 1;
	if (i <= 0) return false;
	int j = n - 1;
	while (a[i-1] >= a[j]) j -= 1;
	swap(a[i - 1], a[j]);
	j = n - 1;
	while (i < j) {
		swap(a[i], a[j]);
		i += 1; j -= 1;
	}
	return true;
}

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

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

	if (next_permutation(p, n)) {
		for (int i = 0; i < n; i++)
			cout << p[i] << ' ';
		cout << '\n';
	}
	else
		cout << -1 << '\n';

	return 0;
}

 

1. A[i-1] < A[i] 만족하는 가장 큰 i 찾기

2. j>=i이면서 A[j] > A[j-1]를 만족하는 가장 큰 j 찾기

3. A[i-1]과 A[j] swap

4. A[i]부터 A[n-1]까지 순열 뒤집기

 -> 이걸 그대로 구현하면 된다. 그냥 생각하긴 좀 헷갈린다. STL을 사용하면 아래와 같이 간단해진다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> p;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		p.push_back(t);
	}

	if (next_permutation(p.begin(), p.end())) {
		for (int i = 0; i < n; i++)
			cout << p[i] << ' ';
		cout << '\n';
	}
	else
		cout << -1 << '\n';

	return 0;
}

 - STL 써야겠지?

 

* 이전 순열 (mid) : 다음 순열에서 부호만 몇 개 바꿔주면 된다.

10973번: 이전 순열

bool prev_permutation(int *a, int n) {
	int i = n - 1;
	while (i > 0 && a[i] >= a[i-1]) i -= 1;
	if (i <= 0) return false;
	int j = n - 1;
	while (a[i - 1] <= a[j]) j -= 1;
	swap(a[i - 1], a[j]);
	j = n - 1;
	while (i < j) {
		swap(a[i], a[j]);
		i += 1; j -= 1;
	}
	return true;
}

 - a[i] < a[i-1] 인 i의 최댓값, a[i-1] > a[j] 인 j의 최댓값을 구하면 된다.

 

 * 모든 순열 (low) : 앞의 문제를 다 해결했다면 쉽다.

10974번: 모든 순열

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> p;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		p.push_back(i+1);
	}

	do {
		for (int i = 0; i < n; i++)
			cout << p[i] << ' ';
		cout << '\n';
	} while (next_permutation(p.begin(), p.end()));

	return 0;
}

 

* 차이를 최대로 (low) : 마찬가지로 앞의 문제만 잘 풀면 쉽게 해결 가능하다

10819번: 차이를 최대로

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> p;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		p.push_back(t);
	}

	sort(p.begin(), p.end());

	int ans = 0;

	do {
		int temp = 0;
		for (int i = 0; i < n - 1; i++)
			temp += abs(p[i] - p[i + 1]);
		if (ans < temp) ans = temp;
	} while (next_permutation(p.begin(), p.end()));

	cout << ans << '\n';

	return 0;
}

 

* 외판원 순회 2 (mid) : TSP라는 유명한 문제란다.

10971번: 외판원 순회 2

 - 일단은 순열을 사용해서 정석대로 풀어봤다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10000000

using namespace std;

int w[10][10];
vector<int> p;

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

	for (int i = 0; i < n; i++) {
		p.push_back(i);
		for (int j = 0; j < n; j++) {
			cin >> w[i][j];
		}
	}

	int ans = MAX;

	do {
		int temp = 0;
		for (int i = 0; i < n - 1; i++) {
			if (w[p[i]][p[i + 1]]) {
				temp += w[p[i]][p[i + 1]];
			}
			else
				temp = MAX;
		}

		if (w[p[n - 1]][p[0]]) {
			temp += w[p[n - 1]][p[0]];
		}
		else
			temp = MAX;

		if (ans > temp) ans = temp;

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

	cout << ans << '\n';

	return 0;
}

 - 주의해야 할 점은 w[i][j] 가 0일 때 경로가 없는 것이므로 예외처리를 해줘야한다는 것과 맨 마지막에서 처음으로 돌아오는 경우를 따로 생각해서 처리해줘야 한다는 것이다.

 - 이렇게도 풀리지만 외판원 문제는 또 다른 특징이 있다. 방문하는 순서대로 p에 저장을 하는데, 그 순서가 몇번째에 오는지는 의미가 없다는 것이다. 예를 들어 설명하면 1->2->3, 2->3->1, 3->1->2 는 다 같은 이동 값을 가진다고 할 수 있다. 따라서 맨 앞에 기준을 하나 설정하고 그 뒤 경우의 최솟값을 구하면, 모든 경우를 구한 것이다.

 - 이를 바탕으로 do 안의 첫번째 for 문이 시작하기 전에 p[0]이 1이 아닌 다른 값일 때 break를 해주면 속도를 훨씬 높일 수 있다.

 

* 로또 (mid) : 1부터 49의 수에서 k개 (6<k<13)를 골라 그 중 6개를 고르는 모든 경우를 구하는 문제다. 

6603번: 로또

 - 순열을 어떻게 이용해야 할지 감이 안 잡혀서 일단 selected를 활용해서 풀어봤다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int a[6];

void go(vector <int> s, int k, int idx, int selected) {
	if (selected == 6) {
		for (int i = 0; i < 6; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}

	if (idx >= k) return;

	a[selected] = s[idx];
	go(s, k, idx + 1, selected + 1);
	a[selected] = 0;
	go(s, k, idx + 1, selected);
}
int main()
{
	int k;
	cin >> k;

	while (k) {
		vector<int> s;
		for (int i = 0; i < k; i++) {
			int t;
			cin >> t;
			s.push_back(t);
		}

		go(s, k, 0, 0);
		cout << '\n';

		cin >> k;
	}


	return 0;
}

 - 해당 수를 고르는 경우와 안 고르는 경우로 나눠 재귀함수로 해결했다.

 - 해설을 보니, 벡터 안에 1을 6개, 0을 n-6개 넣고, 이를 순열로 생각해서 1이 들어가는 위치의 수는 더해주는 식으로 푸는 문제였다. 코드는 굳이 안 넣어도 될 것 같다.

-

브루트 포스가 은근 양이 많은 것 같다. 예제 위주로 풀어서 그런지 시간이 많이 소요된다.

어떻게든 풀어보려고 시간을 쓰는데, 전에도 말했지만 너무 많은 시간을 낭비하지는 말자.

어느정도 보고도 도저히 감이 안 잡히면, 해설을 보고나서 다시 풀어보면 된다.

이제 브루트 포스는 2단원 남았다. 꾸준히 잘 하고 있고, 계속 해보자.

정리 끝!