백준 알고리즘 중급 - 브루트 포스 : 순열 (연습)

잔잔한 꿀팁들

드디어 중급 강의 시작!

오픽의 늪에서 드디어 벗어났다. 다시 차근차근 알고리즘 공부 해보자.

처음엔 많이 헤맸는데, 요령을 알고 나니까 술술 풀렸던 파트였다.

그리고 몇가지 기억하면 좋을 꿀팁들이 있었다. 정리 잘 해뒀다가 나중에 문제 풀 때 써먹자.

정리 시작!

-

* 부등호 (mid) : 앞에서 풀었던 부등호 문제를 순열을 이용해 풀어보자,

2529번: 부등호

- 브루트 포스를 사용한다면, 최댓값은 9부터 제시된 부등호 개수 + 1 만큼의 수를 모두 배열해서 부등호를 성립하는 값을, 최솟값은 0부터 제시된 부등호 개수 + 1 만큼의 수를 모두 배열해서 부등호를 성립하는 값을 구하면 된다.

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

bool check(vector<int> &a, char b[]) {
	for (int i = 0; i < a.size() - 1; i++) {
		if (b[i] == '>' && a[i] < a[i + 1])
			return false;
		if (b[i] == '<' && a[i] > a[i + 1])
			return false;
	}
	return true;
}

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

	char boo[9];
	for (int i = 0; i < k; i++)
		cin >> boo[i];

	vector<int> big, small;
	for (int i = 9; i > 9 - k - 1; i--)
		big.push_back(i);

	for (int i = 0; i < k + 1; i++)
		small.push_back(i);

	do {
		if (check(big, boo))
			break;
	} while (prev_permutation(big.begin(), big.end()));

	do {
		if (check(small, boo))
			break;
	} while (next_permutation(small.begin(), small.end()));

	for (int i = 0; i < k+1; i++)
		cout << big[i];
	cout << '\n';

	for (int i = 0; i < k+1; i++)
		cout << small[i];
	cout << '\n';

	return 0;
}

 - 이게 브루트 포스 순열 문제 풀이의 기본 틀이다. 처음엔 좀 헤맸는데, 익히고 나니까 문제 풀이가 굉장히 편해졌다.

 - 잘 기억해뒀다가 브루트 포스로 해결 가능한 문제 해결에 써먹자.

 

* 단어 수학 (high) : 제일 어려웠다. 단어를 수로 바꾼다고 할 때의 최댓값을 구하는 문제다.

1339번: 단어 수학

- 여러 수가 주어지는데 이 값들을 어떻게 따로 계산할지가 좀 막막했다. 결국 최댓값을 구하는 것이므로 어떤 식으로 중복을 생각해주느냐, 합은 어떻게 구할 것이냐가 관건이었다.

- 코드를 보면서 설명을 해보자. 이 코드에 기억하고 넘어가야 할 것들이 꽤나 있었다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int alpha[256];
int calc(vector <string> &a, vector <char> &letters, vector <int> &d) {
	int m = letters.size();
	int sum = 0;
	for (int i = 0; i < m; i++) {
		alpha[letters[i]] = d[i];
	}
	for (string s : a) {
		int now = 0;
		for (char x : s) {
			now = now * 10 + alpha[x];
		}
		sum += now;
	}
	return sum;
}

int main()
{
	int n;
	cin >> n;
	vector <string> a(n);
	vector <char> letters;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (char x : a[i]) {
			letters.push_back(x);
		}
	}
	sort(letters.begin(), letters.end());
	letters.erase(unique(letters.begin(), letters.end()), letters.end());
	int m = letters.size();
	vector<int> d;
	for (int i = 9; i > 9 - m; i--) {
		d.push_back(i);
	}
	sort(d.begin(), d.end());
	int ans = 0;
	do {
		int now = calc(a, letters, d);
		if (ans < now) {
			ans = now;
		}
	} while (next_permutation(d.begin(), d.end()));
	cout << ans << '\n';
	return 0;
}

 - 먼저 단어의 개수를 받고, 단어를 따로 저장하지 않고 한곳에 저장한다.

 - 여기서 한곳에 저장된 벡터 안의 중복을 제거하는 방법을 기억해두자. unique 함수만 사용하면 연속된 값을 다 뒤쪽으로 보낸다. 바뀌는 부분은 중복을 제거한 수의 길이만큼이고, 그 뒤는 변하지 않는다. 앞쪽에는 중복이 제거된 값이 오고 뒤에는 이전의 값이 오는 좀 지저분한 모양새를 갖춘다.

 - 우리가 필요한 건 중복이 제거된 수만 나열된 부분이니까, 그 뒷부분은 제거해준다. 따라서 이와 같이 실행한다.

 a.erase(unique(a.begin(), a.end())), a.end()) <= unique를 사용하면 중복을 제거한 다음 부분을 가르키고 있으므로 거기서 끝까지 지워주면 원하는 값을 얻을 수 있다.

 - 또한 알파벳 별로 수를 어떻게 할당하는지 살펴보자. 계산의 편의를 위해 배열의 크기를 256으로 잡고 아스키 코드로 바로 계산해줬다. 추가적인 계산을 할 필요 없이 문자 별로 수를 할당할 수 있다. 자리수 계산은 누적 합에 10을 곱하고 해당 수를 더해주는 과정을 반복한다.

 - 여기서 한번 고생을 하고 나니, 뒤에 나올 문제들은 비교적 쉽게 해결했던 것 같다.

 

* 연산자 끼워넣기 (mid) : 위의 요령을 그대로 활용하면 어렵지 않게 풀린다.

14888번: 연산자 끼워넣기

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

int cal(int a[], vector<int> &op) {
	int ans = a[0];
	for (int i = 0; i < op.size(); i++) {
		int temp;
		if (op[i] == 1) {
			temp = ans + a[i + 1];
		} else if (op[i] == 2) {
			temp = ans - a[i + 1];
		} else if (op[i] == 3) {
			temp = ans * a[i + 1];
		} else if (op[i] == 4) {
			temp = ans / a[i + 1];
		}
		ans = temp;
	}
	return ans;
}

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

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

	int p;
	vector<int> op;
	for (int i = 1; i <= 4; i++) {
		cin >> p;
		for (int j = 0; j < p; j++) {
			op.push_back(i);
		}
	}

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

	int ans_max = -1000000000;
	int ans_min = 1000000000;

	do {
		int now = cal(a, op);
		ans_max = max(ans_max, now);
		ans_min = min(ans_min, now);
	} while (next_permutation(op.begin(), op.end()));
	
	cout << ans_max << '\n';
	cout << ans_min << '\n';

	return 0;
}

 - 함수를 처음에 설계할 때 생각을 잘 해서 더 빨리 짜는 연습을 하자. 잔실수로 시간을 많이 허비하는 느낌이 든다.

 

* 스타트와 링크 (mid) : 앞에서 풀었던 문제를 순열을 이용해서 풀어보자.

14889번: 스타트와 링크

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

int calc(int a[][20], vector<int> &t) {
	int t0 = 0, t1 = 0;
	for (int i = 0; i < t.size(); i++) {
		for (int j = 0; j < t.size(); j++) {
			if (i != j && t[i] == t[j]) {
				if (t[i] == 0) {
					t0 += a[i][j];
				}
				else {
					t1 += a[i][j];
				}
			}
		}
	}

	int ans = abs(t0 - t1);
	return ans;
}

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

	int a[20][20];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}

	vector<int> team;
	for (int i = 0; i < n / 2; i++) {
		team.push_back(0);
		team.push_back(1);
	}
	sort(team.begin(), team.end());

	int ans_min = 40000;
	do {
		int now = calc(a, team);
		ans_min = min(ans_min, now);
	} while (next_permutation(team.begin(), team.end()));

	cout << ans_min << '\n';

	return 0;
}

 - 문제는 풀리지만 시간이 꽤 많이 소요된다. 정답 코드도 같이 참고해보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> b(n);
    for (int i=0; i<n/2; i++) {
        b[i] = 1;
    }
    sort(b.begin(), b.end());
    int ans = 2147483647;
    do {
        vector<int> first, second;
        for (int i=0; i<n; i++) {
            if (b[i] == 0) {
                first.push_back(i);
            } else {
                second.push_back(i);
            }
        }
        int one = 0;
        int two = 0;
        for (int i=0; i<n/2; i++) {
            for (int j=0; j<n/2; j++) {
                if (i == j) continue;
                one += a[first[i]][first[j]];
                two += a[second[i]][second[j]];
            }
        }
        int diff = one-two;
        if (diff < 0) diff = -diff;
        if (ans > diff) ans = diff;
    } while(next_permutation(b.begin(), b.end()));
    cout << ans << '\n';
    return 0;
}

 - 두 팀으로 나눠서 수를 저장해준다. 어차피 반반씩 나눠질 거니까 n/2 * n/2 만큼만 계산해주면 각 팀의 값을 구할 수 있다. 이렇게 하면 아까 방법보다 계산 시간을 절반으로 줄일 수 있다.

-

이런저런 꿀팁들이 많았던 파트다. 기억해뒀다가 잘 써먹도록 하자.

중급 출발이 좋다. 기초에서 쌓아올린 기본 개념들이 있다보니 훨씬 수월하다.

더욱 다양한 문제를 풀어보면서 풀이 능력을 길러보자.

정리 끝!