랜덤으로 문제 풀기

작성일 | In

서론

알고리즘 문제를 풀 때 랜덤을 사용해 문제를 해결하는 경우가 있습니다.
최악의 시간 복잡도와 평균 시간 복잡도가 많이 차이나는 알고리즘을 사용하는 경우에 최악의 상황을 피할 때 사용하기도 하고, 무작위 선택을 여러 번 시도하는 것으로 틀릴 확률을 줄이는 용도로 사용하기도 합니다.
이 글에서는 랜덤을 이용해 여러가지 문제를 통해 문제 풀이에 랜덤을 적용하는 방법을 다룹니다.

목차

  • 랜덤을 이용해 평균 복잡도 보장시키기
    • 퀵정렬
    • Smallest Enclosing Circle
    • 재밌는 인터랙티브 문제
    • BOJ18192 보고 정렬
  • 랜덤을 여러 번 시도해 틀릴 확률 줄이기
    • BOJ10523 직선 찾기
    • BOJ2912 백설공주와 난쟁이
  • 더 알아보기
  • 참고 문헌

퀵정렬

최악의 경우와 평균적인 경우에 시간 복잡도가 차이나는 대표적인 알고리즘입니다. 최악의 경우에는 시간 복잡도가 $O(N^2)$이 되고, 평균적인 경우에는 $O(N log N)$이 됩니다. 대부분의 정렬 문제에서는 최악의 경우가 발생하는 채점 데이터를 사용해 퀵정렬을 이용한 풀이를 틀리게 합니다.

퀵정렬을 이용하면서 TLE를 피할 방법은 생각해보면 매우 간단합니다. 최악의 경우가 발생하지 않도록 하면 되는 것이고, 이것은 배열을 섞어주는 것으로 해결할 수 있습니다.

C++ STL에 배열을 섞어주는 random_shuffle(reference)이라는 함수가 존재하므로, 이 함수를 이용하면 쉽게 최악의 경우를 피할 수 있습니다.

아래 코드는 BOJ2751 수 정렬하기 2 (링크)에서 AC를 받은 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int arr[1000000];

void f(int s, int e) {
	if (s >= e) return;
    int pv = arr[s];
    int i = s, j = e;
    while(i < j){
        while(arr[i] <= pv && i < j) i++;
        while(arr[j] >= pv && i < j) j--;
        if(i < j) swap(arr[i], arr[j]);
    }
    if(pv < arr[i]){
        swap(arr[s], arr[i-1]);
        f(s, i-2); f(i, e);
    }else{
        swap(arr[s], arr[i]);
        f(s, i-1); f(i+1, e);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    random_shuffle(arr, arr+n);
    f(0, n-1);
    for(int i=0; i<n; i++) cout << arr[i] << "\n";
}

배열을 안 섞어주면 TLE를 받게 됩니다. (코드)

Smallest Enclosing Circle

최소 외접원 문제(Smallest Enclosing Circle)은 2차원 평면 상에 N개의 점이 주어지면, 이 점들을 모두 포함하는 가장 작은 원을 찾는 문제입니다.
$O(N^4)$풀이를 찾고 이를 발전시켜 $O(N^3)$풀이를 찾은 뒤, $O(N)$으로 줄여보도록 하겠습니다.

본격적으로 문제를 풀기 전에 몇 가지 관찰을 해야합니다.

  1. 2개 이상의 점이 최소 외접원의 둘레 위에 있습니다.

    0개 혹은 1개만 있는 경우, 반지름을 조금 줄이고 원의 중심을 적절히 이동해 2개 이상을 포함하도록 만들 수 있습니다.

  2. 최소 외접원의 둘레 위에 정확히 2개의 점만 있는 경우, 원의 중심은 그 두 점의 중점에 위치합니다.

    1번과 마찬가지로 반지름을 조금 줄이고 중심을 적절히 이동하면 더 작은 원을 만들 수 있습니다.

  3. 최소 외접원의 둘레 위에 3개 이상의 점이 있는 경우, 최소 외접원은 임의의 세 점으로 만든 삼각형의 외접원이 됩니다.

    점 3개를 알면 외접원을 구할 수 있고, 유일합니다.

위 3가지 관찰을 이용해 2개의 점으로 만든 원 $_NC_2$가지와 3개의 점으로 만든 $_NC_3$가지를 각각 모두 검사해서 $O(N^4)$에 문제를 해결할 수 있습니다.

~

우리가 고려해야하는 원의 개수는 $O(N^3)$입니다. 여기서 점 하나를 고정하면 $O(N^2)$개가 되고, 하나를 더 고정하면 $O(N)$개가 됩니다.

여기에서 한 가지 관찰을 더 할 수 있습니다.

두 점을 고정했을 때 봐야하는 원의 중심은 한 직선(두 점을 잇는 선분의 수직 이등분선) 위에 있다.

두 점 p, q를 고정해서 해당 점들을 포함하는 외접원을 구한다고 하면, p와 q를 잇는 직선과 가장 중심이 멀리 떨어진 것만 보면 됩니다.

이것은 두 점을 고정한 다음, 점들을 하나씩 추가하면서 원을 확장하는 방식으로 구현할 수 있습니다. 원에 포함되지 않은 점이 나올 때마다 원을 키워주면 됩니다.
두 점을 고정하는 $O(N^2)$가지 경우에 대해 각각 $O(N)$, 총 $O(N^3)$에 최소 외접원을 찾을 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef pair<long double, long double> pt;
struct Circle{ pt p; double r; };

pt operator + (pt a, pt b){ return pt(a.x + b.x, a.y + b.y); }
pt operator - (pt a, pt b){ return pt(a.x - b.x, a.y - b.y); }
pt operator - (pt a){ return pt(-a.x, -a.y); }
pt operator * (long double a, pt b){ return pt(a*b.x, a*b.y); }
long double operator * (pt a, pt b){ return a.x*a.x + a.y*a.y; } //내적
long double operator / (pt a, pt b){ return a.x*b.y - a.y*b.x; } //외적
long double dst(pt a, pt b){
    auto dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

pt getCenter(pt a, pt b){ return pt((a.x+b.x)/2, (a.y+b.y)/2); } //두 점의 중점
pt getCenter(pt a, pt b, pt c){ //세 점의 외접원의 중심
    pt aa = b - a, bb = c - a;
    auto c1 = aa*aa * 0.5, c2 = bb*bb * 0.5;
    auto d = aa / bb;
    auto x = a.x + (c1 * bb.y - c2 * aa.y) / d;
    auto y = a.y + (c2 * aa.x - c1 * bb.x) / d;
    return pt(x, y);
}

Circle solve(vector<pt> v){
    pt p = {0, 0};
    double r = 0; int n = v.size();
    for(int i=0; i<n; i++) if(dst(p, v[i]) > r){ //break point 1
        p = v[i]; r = 0;
        for(int j=0; j<i; j++) if(dst(p, v[j]) > r){ //break point 2
            p = getCenter(v[i], v[j]); r = dst(p, v[i]);
            for(int k=0; k<j; k++) if(dst(p, v[k]) > r){ //break point 3
                p = getCenter(v[i], v[j], v[k]);
                r = dst(v[k], p);
            }
        }
    }
    return {p, r};
}

solve함수의 각 for문에는 각각 if문이 하나씩 같이 달려있고, 3개의 if문에 의해 걸러져 3개의 for문을 수행하지 않은 경우가 꽤 많습니다.

break point 2에 있는 조건 if(dst(p, v[j]) > r)를 통과해 안쪽으로 들어갈 확률은 평균 $O(\frac {1}{j})$이고, 들어간 경우에 break point 3에 있는 반복문에서 $O(j)$시간이 걸립니다. 즉, break point 2에 있는 반복문의 평균 시간 복잡도는 $O(1)$이 됩니다.
break point 1에 있는 반복문의 내부에서 평균 시간 복잡도가 $O(1)$이므로, 전체의 평균 시간 복잡도는 $O(N)$입니다.

퀵정렬에서 사용했던 것처럼, 평균 시간 복잡도에 동작하도록 배열을 섞어주면 TLE를 피할 수 있습니다.

재밌는 인터랙티브 문제

다음과 같은 인터렉티브 문제를 생각해봅시다.

1e18 이하의 양의 정수로 이루어진 길이 N(1≤N≤1e5)짜리 배열 A가 있을 때, 여러분은 아래 question함수를 최대 103000번 이용해 배열의 최댓값을 구해야합니다.

bool question(int x, long long v) : $A_x ≥ v$ 여부 반환

Naive한 방법으로는, 각 수에 대해 이분탐색을 진행해 값을 알아내서 최댓값을 구하면 됩니다. question함수를 $O(N log 10^{18})$번 호출하게 됩니다.

여기에서 약간의 커팅을 시도할 수 있습니다. 현재까지 봤던 수의 최댓값보다 작거나 같은 수에 대해서는 굳이 이분 탐색을 하지 않아도 됩니다.
만약 배열이 내림차순으로 정렬된 경우에는 $N + O(log 10^{18})$번으로 커팅이 잘 되며, 오름차순으로 정렬된 경우에는 $O(N log 10^{18})$번으로 커팅이 되지 않습니다. 평균적인 경우에는 어떨지 알아봅시다.

일단 최댓값을 찾은 경우, 오른쪽에 있는 수에 대해서는 이분 탐색을 하지 않아도 됩니다. 최댓값 위치의 기댓값은 배열의 중앙입니다. 최댓값보다 왼쪽에 있는 수를 봅시다.
최댓값보다 왼쪽에 있는 수 중에서 가장 큰 값을 만나게 되면, 배열 전체의 최댓값을 만나기 전까지는 이분 탐색을 수행하지 않습니다. 이러한 값의 위치의 기댓값은 첫 번째 원소와 최댓값의 중앙입니다.

이런식으로 탐색할 구간에서 최댓값 위치의 기댓값이 중앙이라는 것을 이용해 평균적으로 $O(log N)$번만 이분 탐색을 하면 된다는 것을 알 수 있고, 평균적으로 $N + O(log N log 10^{18})$번의 함수 호출로 해결할 수 있습니다.

위 2문제에서 했던 것처럼, 탐색 순서를 섞어주는 것으로 평균 복잡도에 동작하도록 만들 수 있습니다.

BOJ18192 보고 정렬

문제 링크

이 문제는 랜덤이 모든 경우를 같은 확률로 발생시킨다는 성질을 이용해 해결합니다.

앞쪽부터 하나씩 맞춰가는 방식을 이용하면 $O(N log N)$번의 함수 호출로 문제를 풀 수 있습니다.
간략하게 알고리즘을 소개하자면 $A_i ≠ i$인 최소 $i$를 찾은 뒤, $A_j = i$를 찾아 $[i, j]$ 구간을 섞어서 $A_i = i$로 만드는 것을 반복하면 됩니다.

$i$를 하나씩 맞춰가는 방식으로 진행이 되며, 총 셔플 횟수는 $\displaystyle \sum_{i=0}^{N-1} (i를\space 맞추는데\space 필요한\space 셔플\space 횟수)$ 가 됩니다.
어떤 수를 왼쪽으로 n칸 옮기는데 필요한 셔플 횟수의 기댓값 $D_n$은 $\displaystyle D_n = \frac {1}{n+1}(\sum_{k=1}^{n}D_k)+1$이고, 식을 정리하면 약 $2 + ln\space n$정도입니다.

그러므로 $O(N log N)$번의 셔플로 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bogoSort.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> v;

bool chk(){
	for(int i=0; i<n; i++) if(v[i] != i) return 0;
	return 1;
}

void sort_array(int N){
	n = N;
	v = copy_array();
	while(1){
		int s = -1, e;
		for(int i=0; i<n; i++) if(v[i] != i){
			s = i; break;
		}
		if(s == -1) break;
		while(v[s] != s){
			for(int i=0; i<n; i++) if(v[i] == s){
				e = i; break;
			}
			shuffle_array(s, e);
			v = copy_array();
		}
	}
}

BOJ10523 직선 찾기

문제 링크

이 문제에서는 랜덤을 이용해 적당한 답을 구하고, 그것을 반복해 틀린 답을 구할 확률을 줄입니다.
이 문제에서 주목해야할 점은 $p≥20$이라는 조건입니다.

이 문제에서 p%, 즉 $\frac {Np}{100}$개 이상이 한 직선 위에 있는지 판단해야 합니다. 그런 직선이 존재하는 경우, 랜덤으로 두 점을 잡아 직선을 만들 때 정답이 되는 직선을 찾을 확률을 알아봅시다.

N개의 점으로 만들 수 있는 직선의 개수는 최대 $\frac {N(N-1)}{2}$입니다. 그중에서 $\frac {Np}{100}$개의 점으로만 만들 수 있는 직선의 개수는 $\frac {\frac {Np}{100}(\frac {Np}{100}-1)}{2} = \frac {N^2p^2-100Np}{20000}$입니다.
그러므로 정답이 되는 직선을 찾을 확률은 $\frac {Np^2-100p}{10000(N-1)}$입니다. 이때 $p≥20$이기 때문에 정답이 되는 직선을 찾을 확률은 $\frac {N-5}{25(N-1)}$ 이상이 되므로 찾지 못할 확률은 약 $\frac {24}{25}$가 됩니다.

이렇게 우리는 랜덤으로 두 점을 잡아 $O(N)$만에 확인하는, 96%의 확률로 틀리는 알고리즘을 만들었습니다!
쓸모없을 것 같지만, K번 반복해주면 틀릴 확률이 $(\frac {24}{25})^K$가 됩니다. K가 커질수록 맞을 확률이 올라가며, 시간 복잡도는 $O(KN)$입니다.

K번 반복을 해서 $\frac {Np}{100}$개 이상의 점을 포함하는 직선을 발견했다면 possible을 출력하고, 발견하지 못했다면 impossible를 출력해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

mt19937 rd((unsigned)chrono::steady_clock::now().time_since_epoch().count());

ll n, per, want;
vector<p> v;
const int k = 100;

ll ccw(p a, p b, p c){
    ll res = a.x*b.y + b.x*c.y + c.x*a.y;
    res -= b.x*a.y + c.x*b.y + a.x*c.y;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}

int cnt(p x, p y){
	int ret = 0;
	for(auto i : v){
		ret += ccw(x, i, y) == 0;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> per; v.resize(n);
	for(auto &i : v) cin >> i.x >> i.y;
    if(n*per%100 == 0) want = n*per/100;
	else want = n*per/100+1;

    if(n == 1){ cout << "possible"; return 0; }
    uniform_int_distribution<int> rnd(0, n-1);

	for(int loop=0; loop<k; loop++){
		int a = rnd(rd);
		int b = rnd(rd);
		while(a == b) b = rnd(rd);
		if(cnt(v[a], v[b]) >= want){
			cout << "possible"; return 0;
		}
	}
	cout << "impossible";
}

BOJ2912 백설공주와 난쟁이

문제 링크

이 문제도 랜덤을 이용해 틀릴 확률을 줄이는 방식을 이용합니다.

쿼리로 들어온 구간의 과반수가 같은 수로 이루어진 경우, 랜덤으로 원소를 선택하면 $\frac {1}{2}$ 이상의 확률로 과반수를 차지하는 수를 선택하게 됩니다. 즉, 틀릴 확률은 $\frac {1}{2}$ 이하가 됩니다.

틀릴 확률이 50%인 알고리즘이지만, K번 반복하면 틀릴 확률이 $\frac {1}{2^K}$인 아주 좋은 알고리즘이 됩니다.

각 수마다 등장하는 인덱스를 정렬된 상태로 저장하면, 특정 구간에 해당 수가 몇 번 나오는지 $O(log N)$만에 알 수 있으므로, 전체 시간 복잡도는 $O(KQlogN)$입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int n, q;
int arr[303030];
vector<int> v[10101];
const int k = 50;

int main(){
	mt19937 rd = mt19937((unsigned)chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for(int i=1; i<=n; i++){
		cin >> arr[i];
		if(v[arr[i]].empty()) v[arr[i]].push_back(-1);
		v[arr[i]].push_back(i);
	}
	cin >> q;
	while(q--){
		int s, e, ans = -1;
		cin >> s >> e;
        uniform_int_distribution<int> rnd(s, e);
		for(int i=1; i<=100; i++){
			int j = rnd(rd);
			int val = arr[j];
			int cnt = upper_bound(v[val].begin(), v[val].end(), e) - lower_bound(v[val].begin(), v[val].end(), s);
			if(cnt > (e-s+1)/2){
				ans = val; break;
			}
		}
		if(ans < 0) cout << "no\n";
		else cout << "yes " << ans << "\n";
	}
}

더 알아보기

Global Min Cut을 랜덤을 사용해 $O(V^2 log^3 V)$만에 $\frac {V-1}{V}$의 확률로 정확한 답을 구할 수 있는 방법이 있습니다. (링크)

Delaunay Triangulation을 랜덤을 사용해 평균 $O(N log log N)$에 구할 수 있습니다.

참고 문헌