230. Randomization

다섯 번째로 무작위화(Randomization)에 대해서 알아본다. 무작위화는 쉽게 설명하면 풀이 중간에 무언가를 선택하는 상황이 있을 때 그것을 정해진 규칙에 따라 하지 않고 무작위로 하는 것이다. 이때 무작위로 선택한 대상으로 문제를 풀면 틀릴 확률이 유의미하게 작아야 한다. 아래의 문제를 예시로 들어 보자.

 

BOJ 2912. PATULJCI (Platinum II)

길이가 $N$인 수열이 주어진다. 이때 $A$번째 ~ $B$번째 원소로 이루어진 구간에 절반 넘게 등장하는 원소가 존재하는지 확인하는 쿼리를 $M$번 처리하라.

$N$은 $3 \times 10^5$, $M \le 10^4$이므로 나이브 풀이는 시간 안에 통과할 가능성이 거의 없다. 여기서 무작위화를 사용하면 다음과 같은 풀이를 낼 수가 있다.

• 구간에 절반 넘게 등장하는 원소가 존재할 경우 유일하다. 이 값을 출력 설명에 나온 대로 $X$라고 하자.
• 쿼리로 주어진 구간 내에서 원소 하나를 무작위로 고른다. 만약 $X$가 존재할 경우, 무작위로 고른 원소가 $X$일 확률은 $\frac{1}{2}$보다 크고, 무작위로 고른 원소가 $X$가 아닐 확률은 $\frac{1}{2}$보다 작다.
• 무작위로 원소를 고르는 시행을 $c$번 했다고 가정하자. 이때 $X$가 존재하는데 $X$를 한 번도 뽑지 못할 확률은 $\frac{1}{2^c}$보다 작다. $c$가 $20$ 정도일 경우 이 값은 $10^{-6}$ 정도밖에 되지 않는다.
• 따라서 앞에서 고른 $c$개의 (중복되었을 수도 있는) 원소들 중에 $X$가 존재할 확률은 $1 - \frac{1}{2^c}$보다 크다. 따라서 고른 원소들 중에 $X$로 가능한 원소가 없었다면 답을 no로 간주한다.
• 임의의 구간에 어떤 원소가 몇 번 등장하는지 빠르게 구할 수 있으면 전체 문제를 해결할 수 있는데, 이것은 각 원소들의 등장 위치를 다 저장해 놓고 거기서 lower_bound와 upper_bound 같은 함수 잘 써 주면 된다.

이 풀이는 $X$가 존재하지 않을 경우 항상 맞고 $X$가 존재할 경우에도 $20$ ~ $30$개의 원소만 뽑아 보면 틀릴 확률이 크게 떨어지기 때문에 충분히 유효하다.

 

인터랙티브 문제의 비중이 약간 높은 편인데, 그만큼 두 유형이 결합된 채로 나오기 쉽다는 것으로 간주하면 된다. 아래의 연습문제를 살펴봐도 절반이 인터랙티브이다.

 

[연습문제]

 

BOJ 10523. Finding Lines (Platinum V)

구하는 직선이 전체 점의 $\frac{1}{5}$을 이상은 지나야 하므로, 정답이 존재하고 임의로 서로 다른 두 점을 골랐을 때 두 점을 지나는 직선이 답이 될 확률은 약 $\frac{1}{25}$ 이상이다. 따라서 이 과정을 $c$번 반복했을 때 답을 찾지 못할 확률은 $\frac{24}{25}^c$ 이하이고, $c$가 $300$ 정도만 되어도 거의 틀리지 않는다.

 

BOJ 21340. Dragon Balls (Platinum V)

임의의 위치를 찾아서 가장 가까운 드래곤볼까지의 거리를 입력받으면 가능한 좌표의 수의 기댓값이 충분히 작기 때문에 적은 횟수의 추측으로도 모든 드래곤볼을 다 찾을 수 있다. 랜덤을 안 쓰는 일부 풀이들은 저격 데이터가 존재하므로 주의하자.

 

BOJ 26001. Jagged Skyline (Platinum III)

무작위로 한 열을 골라서 그 열 빌딩의 꼭대기를 이분 탐색으로 찾고, 그보다 더 높은 빌딩이 존재할 가능성이 있는 열들 중에서 한 열을 무작위로 고르는 과정은 더 높은 빌딩을 찾거나 그러한 경우가 없을 때까지 반복한다. 만약 더 높은 빌딩을 찾았다면 다시 그 빌딩의 꼭대기를 이분 탐색으로 찾는 식으로 계속 반복하면 된다.

 

BOJ 11744. Jump (Platinum III)

무작위로 아무 비트 문자열을 출력하면 약 $\frac{1}{40}$의 확률로 $OneMax(Q) = \frac{n}{2}$가 된다. 따라서 $500$번 정도 시도하면 거의 $100%$의 확률로 그런 문자열을 찾을 수 있고, 그 문자열에서 나머지 $n$번의 쿼리로 $S$를 찾으면 된다. 이 부분은 두 자리를 최대 두 번의 쿼리로 알아내는 방식으로 접근할 수 있다.

 

BOJ 10124. Couriers (Platinum I)

2912번과 같은데 제한이 커서 랜덤 실행 횟수를 조금 줄여야 할 수도 있다.

 

BOJ 21341. Endgame (Platinum I)

Alice가 이기는 경우는 set 등을 이용해서 $O(n \lg n)$ 시간에 처리할 수 있다. 그러면 Tie가 되는 경우와 Bob이 이기는 경우가 남는데, 여기서 랜덤을 사용할 수 있다. 보드 전체의 칸 수는 $n^2$이고 두 번 이하의 이동으로 가능한 경우의 수는 (두 이동의 순서만 바뀐 경우를 제외하면) $\frac{1}{2} n^2$보다 약간 크므로($n$이 작으면 비율이 많이 달라지지만 이런 경우는 랜덤으로 칸을 고르는 과정을 조금만 반복해도 거의 모든 칸을 다 고를 수 있어서 큰 문제가 되지 않는다) $n$이 충분히 크면 Alice의 기물이 임의의 칸으로 이동했을 때 무승부가 날 확률이 $\frac{1}{2}$ 정도라는 것을 알 수 있다. 따라서 무작위로 몇십 개의 칸만 확인해 보면 된다.

 

→ solved.ac tag: randomization