무작위화 알고리즘 문제 풀이 모음 220903
백준 BOJ 12041번 : Password Security (Small 2)
문제 난이도 : Gold III
알고리즘 분류 : 무작위화, 구성적
모든 대문자 알파벳을 하나씩 사용하여 26자리 비밀번호를 만들 때, 해당 비밀번호가 N개의 주어진 문자열을 포함하지 않도록 만드는 문제이다.
1 ~ 26으로 이루어진 순열을 무작위로 만든 뒤, 이 순열에 해당하는 문자열이 N개의 문자열을 포함하지 않을 때까지 돌리면 된다.
문제는 아예 불가능한 경우가 있는데, 이를 해결하기 위해 1만번까지는 돌려보고, 그래도 해당하는 정답이 없으면 impossible로 간주해주면 모든 테스트케이스를 통과할 수 있다.
(참고로 1천번은 넉넉하지 않아 WA를 받을 확률이 높다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, INT_MAX);
auto rd = bind(uid, mt);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N; cin >> N;
vector<string> v(N);
for(int i=0; i<N; i++) cin >> v[i];
bool found = false;
for(int r=0; r<1e4; r++) {
vector<int> u;
vector<bool> w(26);
while(u.size() < 26) {
int x = rd() % 26;
if(!w[x]) {
u.push_back(x);
w[x] = true;
}
}
string str = "";
for(int i=0; i<u.size(); i++) str += char('A' + u[i]);
bool check = true;
for(int i=0; i<N; i++)
if(str.find(v[i]) >= 0 && str.find(v[i]) < str.length()) check = false;
if(check) {
cout << "Case #" << t << ": " << str << "\n";
found = true;
break;
}
}
if(!found) cout << "Case #" << t << ": IMPOSSIBLE\n";
}
}
같은 코드로 백준 BOJ 12040번 : Password Security (Small 1)을 풀 수 있다.
백준 BOJ 18205번 : Farming Mars
문제 난이도 : Gold IV
알고리즘 분류 : 무작위화, 값/좌표 압축
N개 토양의 산성도가 주어지고, 사용할 수 있는 땅이란 그 구간에서 절반보다 많은 값들이 동일한 산성도를 가지는 땅이라고 할 때, M개 쿼리에 대해 [l, r] 구간을 사용할 수 있는지 구하는 문제이다.
백준 BOJ 2912번 : 백설공주와 난쟁이에서 풀었던 방식과 똑같이 구현했다.
다만 여기서는 소수점 아래 6자리까지 비교해야하므로, 1e6을 곱해준 뒤 좌표 압축을 해주었다.
브루트포스로 돌아간다고 한다. (범위만 조금 더 컸어도 비슷한 문제가 있어 나름 꿀문제인데..)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, INT_MAX);
auto rd = bind(uid, mt);
int N, M; cin >> N >> M;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) {
double x; cin >> x;
int y = x * 1e6;
v[i] = u[i] = y;
}
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
vector<int> w(N);
for(int i=0; i<v.size(); i++)
w[i] = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
vector<vector<int>> vv(1e4 + 1);
for(int i=0; i<N; i++) vv[w[i]].push_back(i);
while(M--) {
int l, r; cin >> l >> r;
l--, r--;
bool check = false;
for(int i=0; i<100; i++) {
int x = w[l + (rd() % (r-l+1))];
int cnt = upper_bound(vv[x].begin(), vv[x].end(), r) - lower_bound(vv[x].begin(), vv[x].end(), l);
if(cnt > (r-l+1)/2) {
cout << "usable\n";
check = true;
break;
}
}
if(!check) cout << "unusable\n";
}
}
백준 BOJ 23271번 : Grzaed Grains
문제 난이도 : Gold IV
알고리즘 분류 : 무작위화
(x, y)를 중심으로 반지름 r인 원이 10개 이하로 존재할 때 이 원들의 합집합의 넓이를 구하는 문제이다. (x, y, r 모두 -10 ~ 10 사이의 정수이며, 답은 오차 범위 10% 이내이기만 하면 된다.)
범위가 매우 작고, 오차 범위는 매우 크다.
이 문제에 한해서만 특이한 방법으로 풀 수가 있는데, 바로 점들을 무작위로 찍어서 포함되는 비율을 이용하여 구하는 것이다.
나의 경우에는 -20 ~ 20 사이의 x, y 좌표에 해당하는 실수를 만들어서 1e6번 찍어보고, 그 중 포함되는 것의 비율을 이용하여 전체 넓이에 대한 비율로 답을 구하였다.
자세한 구현은 아래의 코드를 참고하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int x, y, r; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, INT_MAX);
auto rd = bind(uid, mt);
int N; cin >> N;
vector<s> v(N);
for(int i=0; i<N; i++)
cin >> v[i].x >> v[i].y >> v[i].r;
int cnt = 0;
for(int att=1; att<=1e6; att++) {
bool check = false;
double x = ((rd() % (int)1e5) / 1e5) * 40 - 20;
double y = ((rd() % (int)1e5) / 1e5) * 40 - 20;
for(int i=0; i<N; i++)
if(pow(x - v[i].x, 2) + pow(y - v[i].y, 2) <= pow(v[i].r, 2)) check = true;
if(check) cnt++;
}
double ans = pow(40, 2) * (cnt / 1e6);
cout << ans << "\n";
}
백준 BOJ 21960번 : Consul
문제 난이도 : Gold V
알고리즘 분류 : 무작위화, 애드 혹 (+ 함수 구현)
N명의 선거인단이 10억명 이하의 후보 중 하나를 뽑았다고 할 때, 쿼리를 50회 이하로 사용하여 N/3보다 큰 인원에게 선발된 후보가 있는지 찾는 문제이다. (있으면 번호를 구하고, 없으면 -1을 제출)
사용할 수 있는 쿼리로는 다음의 것이 있다.
kth(int i) : i번째 후보가 뽑은 후보의 번호를 리턴
cnt(int x) : x번 후보가 뽑힌 횟수
say_answer(int a) : 답을 a로 제출
만약 N/3회 이상 뽑힌 사람이 있다면, 랜덤으로 아무 유권자나 뽑아서 그 사람이 뽑은 번호가 N/3회 이상 나왔는지 확인해보면 되고, 한 번 검사마다 1/3의 확률로 답이 나온다. (이 때 쿼리는 cnt(kth(x))로 하면 되고, 이 때 쿼리는 2회 사용된다.)
따라서 이러한 수행을 최대한으로, 예를 들어 10번 해준다고 치면 답이 얻어질 확률은 1 - (2/3)^10으로 거의 무조건 답을 얻을 수 있다.
이제 최대 쿼리 개수만 찾아주면 되는데, 1번 서브테스크에서 Q ≤ 50 이하여야 만점이라고 하였으므로, 대략 24회 정도 cnt(kth(x))을 사용해주면 된다.
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int kth(int k);
void say_answer(int k);
int cnt(int k);
void solve(int n)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, 1e5);
auto rd = bind(uid, mt);
bool check = false;
for(int i=0; i<24; i++) {
int x = rd() % n + 1;
if(cnt(kth(x)) > n/3) {
say_answer(kth(x));
check = true;
break;
}
}
if(!check) say_answer(-1);
}
백준 BOJ 15860번 : Ninety-nine
문제 난이도 : Silver III
알고리즘 분류 : 게임 이론, 인터랙티브 (+ 무작위화)
0에서부터 시작하여 프로그램과 번갈아가며 1 또는 2를 더해서 99를 먼저 완성하는 인터랙티브 문제이다.
원래라면 3의 배수만 불러주면 되는데, 내가 먼저 시작하는 입장이기 때문에 최소한 한 번은 뒤집어야 한다.
그렇기 때문에 일단은 무작위로 1 또는 2를 더해서 출력하다가, 3의 배수를 취할 수 있으면 바로 취해주는 방식을 택한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, INT_MAX);
auto rd = bind(uid, mt);
int x = 0;
while(true) {
if(x % 3 == 0) x += (rd() % 2 + 1);
else if(x % 3 == 1) x += 2;
else if(x % 3 == 2) x += 1;
cout << x << endl;
if(x >= 99) break;
cin >> x;
if(x >= 99) break;
}
}
백준 BOJ 16972번 : 814 - 1
문제 난이도 : Bronze I
알고리즘 분류 : 무작위화
2차원 좌표 평면 상의 814개의 점들을 두 점의 거리가 같은 쌍이 존재하지 않도록 출력하는 문제이다.
이 때 모든 점들의 좌표는 -8140 ~ 8140 사이의 정수여야 한다.
mt19937을 이용하여 랜덤으로 814개의 점들을 출력해주면 대부분 맞는다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, INT_MAX);
auto rd = bind(uid, mt);
for(int i=0; i<814; i++)
cout << (rd() % 16280) - 8140 << " " << (rd() % 16280) - 8140 << "\n";
}
백준 BOJ 20067번 : Nowruz 1
문제 난이도 : Gold V
알고리즘 분류 : 무작위화, 구성적
이 문제는 무작위화를 이용해서 풀려다가 실패해서 아래에 배치한다.
N x M 크기의 배열이 주어지고, 점이 있는 위치에 X들을 적절히 배치해서 모든 점들 사이의 경로가 유일하며, 막다른 길(점 주위의 3칸이 # 또는 X로 둘러싸임)이 K개 만들어지도록 하는 문제이다.
1 ~ 10까지 문제가 있는데 1번 문제의 경우에는 범위가 작아서 노가다로 풀 수 있다.
X.X.#.X.X.X#.X#X
..#.............
X...X.X.X.X#.X.X
..XX.X##.XX.X..#
X##..........X..
....XX.XX.#.X..X
X.X##...X..X..#X
...X.X.XXX..X...
X.X.....X..X.X.X
...X.#.X.X...X..
X.X.XX....#X.X.X
....X..X.XX..X.X
#.X.XX.X#XXX.X..
...XX.X.X.X.XX.X
X#..............
XX.X.X.X.X.X.XXX