최빈값 문제에 대한 고찰

최빈값 문제에 대한 고찰

최빈값 문제에 대한 고찰.pdf

0.51MB

중복을 허용하는 집합인 multiset $S$에 대해, $S$에서 $x$가 등장하는 횟수를 ${\rm freq}_S(x)$라고 씁시다. 모든 $x \in S$에 대해서, ${\rm freq}_S(x) \le {\rm freq}_S (a)$를 만족하는 경우에, $S$를 최빈값이라고 부릅니다. $S$의 최빈값은 여럿일 수는 있지만, 최빈값이 등장하는 개수인 $m$은 유일합니다.

우리는 다음 문제에 관심이 있습니다.

• 배열 $A$가 주어졌을 때, 배열의 $i$번째부터 $j$번째까지 원소인 $A[i:j]$의 최빈값을 효율적으로 구할 수 있을까?

이 글에서는 다음 주제에 대해서 다룹니다.

• 배열 $A$의 최빈값을 찾는 방법
• 특수한 경우를 효율적으로 해결하는 방법
  • ${\rm freq}_S(x) > \alpha |S|$인 $x$를 확률적으로 찾는 방법
  • 다수자 투표, $\alpha = 1/2$일 때 찾는 방법
• 일반적 경우를 효율적으로 해결하는 방법
  • 배열의 길이가 $N$일 때, 공간 복잡도 $O(N)$, 시간 복잡도 초기화 $O(N \sqrt{N})$, 쿼리당 $O(\sqrt{N})$
• 길이가 $O(N)$이고, 사전에 주어진 $O(N)$개의 쿼리를 답하는 데에, $O(N^{1.5-\epsilon})$ 시간을 달성하기 힘든 이유

배열의 최빈값을 찾는 방법

배열의 원소가 임의의 값일 때, $1$ 이상 $N$ 이하의 수로 배열의 원소를 바꾸려고 합니다. 이는 배열을 $O(N \log N)$시간에 정렬한 뒤, 중복을 제거한 뒤 남은 값에 대해서 $1$부터 차례로 번호를 붙여나가면 됩니다. 이 경우에, 최빈값이 등장하는 횟수는 동일하고, 최빈값을 찾는 것도 길이 $N$의 배열을 사용하면 쉽게 구할 수 있습니다.

이후에는 일반적인 상황을 가정합시다. 우리가 다룰 배열 $A$의 길이는 $N$이고, 배열의 원소는 $1$ 이상 $N$ 이하입니다. 다음의 간단하지만, 핵심적인 보조정리부터 시작합시다.

• 보조정리 1. $A$와 $B$가 multiset이라고 합시다. $c$가 $A \cup B$의 최빈값이고, $c \not \in A$인 경우, $c$는 $B$의 최빈값입니다.

보조정리 1의 증명. 임의의 원소 $x \in B$에 대해, ${\rm freq}_B(c) = {\rm freq}(c) \ge {\rm freq}_{A \cup B}(x) \ge {\rm freq}_{B}(x)$입니다. $\square$

이 보조정리를 다른 방식으로 작성하면 다음과 같습니다.

• 보조정리 1'. $A$와 $B$가 multiset이라고 합시다. $A \cup B$의 최빈값은, $A$의 원소이거나 $B$의 최빈값입니다.

이제 우리는 가장 기본적인 알고리즘 하나를 제시할 것입니다.

• 정리 1. $A$의 최빈값은 시간 복잡도 $O(N)$에 구할 수 있습니다.

정리 1의 증명. 최빈값과 각 수가 등장하는 횟수는 같은 알고리즘으로 구할 수 있습니다.

$A[1:i]$의 최빈값과 각 수가 등장하는 횟수를 구했다고 합시다.

• $A[1:i+1]$에서 각 수가 등장하는 횟수는, $A[1:i]$에서 $A[i+1]$만 한 번 더 등장하기 때문에, $O(1)$시간에 갱신할 수 있습니다.
• 보조정리 1'에 의해, $A[1:i+1]$의 최빈값은, $A[1:i]$의 최빈값이거나, 혹은 $A[i+1]$입니다.
  • $A[1:i+1]$의 각 수가 등장하는 횟수를 알고 있으므로, $A[1:i]$의 최빈값과 $A[i+1]$ 중 더 많이 등장하는 수를 최빈값으로 사용합니다.

위의 알고리즘을, $i=1, \cdots, N$까지 반복하면 $A$의 최빈값과 $A$에서 각 수가 등장하는 횟수를 계산할 수 있습니다. $\square$

특수한 경우를 효율적으로 해결하는 방법

이 알고리즘을 개선해봅시다. 다음과 같은 간단한 자료구조를 생각합시다.

• 보조정리 2. 배열 $A$에서 $i$번째부터 $j$번째까지, $v$가 몇 번 등장하는지 여부를, 전처리 $O(N)$, $(i, j, v)$에 대한 쿼리 $O(\log N)$의 시간으로 찾을 수 있습니다.

보조정리 2의 증명. $1$ 이상 $N$ 이하의 모든 수 $v$에 대해서, 각 수가 등장하는 위치가 정렬된 배열 $P_v$를 저장합니다. 이는 $O(N)$시간에 계산할 수 있습니다. 이제 $P_v$에서 $i$ 이상 $j$ 이하인 수가 몇 번 등장하는지를 계산하는 문제가 됩니다. 이는 이분탐색으로 구할 수 있고, 시간 복잡도는 $O(\log N)$입니다. $\square$

참고. 균형 이진 탐색 트리 등을 사용하여, 수의 변경을 포함하여 $O(\log N)$으로 처리할 수 있습니다. Van Emde Boas Tree 등을 사용하면, $O(\log \log N)$ 등에도 처리할 수 있습니다.

 

이제, 다음의 확률론적 알고리즘을 제시합니다.

• 정리 2. $S$를 $A$의 $i$부터 $j$번째 까지 배열의 원소라고 합시다. ${\rm freq}_S(x) > \alpha |S|$를 만족하는 $x$는(혹은 존재하는지의 여부는), 전처리 $O(N)$, $p$ 이상의 확률로 $O(f(\alpha; p) \log N)$ 시간에 찾을 수 있습니다. 여기서 $f(\alpha; p) = \log_{(1-\alpha)} \frac{1}{1-p}$ 입니다.

정리 2의 증명. 이제 위 자료구조를 이용해서, 다음과 같은 단순한 알고리즘을 제시합니다.

• $A[i:j]$에서 임의의 위치에서 수를 하나 뽑아, 해당 수가 $\alpha(j-i+1)$번 초과로 등장하는지 확인하는 것을, $K$번 반복합니다.

이 알고리즘의 답 $v$가 존재하는 경우, 임의로 뽑힌 수가 $v$일 확률은 $\alpha$ 초과입니다. 즉, 이 알고리즘이 한 번의 시행에 답을 찾지 못할 확률은 $1- \alpha$미만입니다. $K$번 모두 답을 찾지 못할 확률은 $(1-\alpha)^K$ 미만이므로, $K > f(\alpha; p)$로 설정할 경우, 이 알고리즘이 답을 찾지 못할 확률이 $1-p$미만입니다.

각 시행은 $O(\log N)$의 시간이 들기 때문에, 총 시간 복잡도는 $O(f(\alpha; p) \log N)$입니다.

이 문제는 $\alpha = 1/2$인 경우에 더 효율적으로 해결할 수 있습니다.

다수자 투표

우리는 어떤 배열에서 절반 초과로 등장하는 원소가 있는지를 구하는 방법에 관심이 있습니다. 이 알고리즘은 추가 공간 복잡도가 $O(1)$이 든다는 장점이 있습니다.

 

정리 3 (Boyer-Moore). $A$에서 절반 초과로 등장하는 원소는(혹은 존재하는지의 여부는), 시간 복잡도 $O(N)$, 공간 복잡도 $O(1)$에 구할 수 있습니다.

 

정리 3의 증명. 다음과 같은 알고리즘을 생각합시다.

• 답 후보 $m$을 정하고, 수를 $i$로 초기화합니다.
• 입력 수열의 각 원소 $x$에 대해서, 다음을 반복합니다.
  • $i = 0$이거나, $m = x$인 경우, $m \leftarrow x$, $i \leftarrow i+1$로 설정합니다.
  • 그렇지 않은 경우, $i \leftarrow i-1$로 설정합니다.
• 최종으로 남은 원소 $m$에 대해서, $m$이 절반 초과로 등장하는지 확인합니다.

이 알고리즘이 올바르게 동작한다는 것은, 다음과 같이 증명할 수 있습니다.

 

보조정리 3. 위 알고리즘의 $(m, i)$에 대해 $i_v$를, $v = m$이면 $i$, 아닌 경우에 $-i$라고 정의합시다. $i_v \ge 2 \times {\rm freq}_A (v) - |A|$입니다.

 

보조정리 3의 증명. 알고리즘의 각 단계에서, 보는 수 $x$가 $v$인 경우에는, 항상 $i_v$가 $1$ 증가하고, $x$가 $v$가 아닌 경우에는 $i_v$가 $1$ 증가 혹은 감소합니다. $i_v$는 최소 ${\rm freq}_A (v)$번 증가하기 때문에, ${\rm freq}_A(v) - (|A| - {\rm freq}_A(v))$인 $2 \times {\rm freq}_A (v) - |A|$ 이상입니다. $\square$

 

보조정리 3에 의해서, $ {\rm freq}_A (v) > |A|/2$이면, $i_v$는 $0$ 초과이고, $v = m$입니다. $\square$

이 알고리즘을 Boyer-Moore 다수자 투표(Boyer-Moore Majority Voting) 알고리즘이라고 합니다.

해당 알고리즘은, 절반 초과로 등장하는 원소에 대한 정보를 $O(1)$ 공간에 담을 수 있게 해 줍니다. 이제, 이 알고리즘을 확장한, 병렬 Boyer-Moore 다수자 투표 알고리즘을 소개합니다. 이 알고리즘은 재귀적으로 정의됩니다. 위에서 소개한 다수자 투표 알고리즘처럼, 이 알고리즘은 $(m, i)$를 반환합니다. 가장 기본적인 경우인, $A = {a}$ 일 때, $(m, i) = (a, 1)$입니다.

병렬 Boyer-Moore 다수자 투표 알고리즘을 이용해서, 어떤 집합 $A$에 대해서 계산한 결과가 $(m^A, i^A)$; $B$에 대해서 계산한 결과가 $(m^B; i^B)$라고 합시다. 이때, 두 결과를 합치는 연산 $\oplus$, $(m^A, i^A) \oplus (m^B, i^B) = (m^{A \cup B}, i^{A \cup B})$를 다음과 같이 구할 수 있습니다:

• $m^A = m^B$ 인 경우: $(m^{A \cup B}, i^{A \cup B}) = (m^A, i^A + i^B)$
• $m^A \ne m^B$이고, $i^A \ge i^B$ 인 경우: $(m^{A \cup B}, i^{A \cup B}) =(m^A, i^A - i^B)$
• $m^A \ne m^B$이고, $i^A < i^B$ 인 경우: $(m^{A \cup B}, i^{A \cup B}) =(m^B, i^B - i^A)$

이 경우에도 보조정리 3과 유사한 보조정리를 이용할 수 있습니다.

 

보조정리 4. 위 알고리즘의 $(m^A, i^A)$에 대해 $i^A_v$를, $v = m$이면 $i$, 아닌 경우에 $-i$라고 정의합시다. $i^A_v \ge 2 \times {\rm freq}_A (v) - |A|$입니다.

 

보조정리 4의 증명.

강한 수학적 귀납법을 사용하여, 병렬 Boyer-Moore 다수자 투표 알고리즘이 올바름을 증명합시다.

$A = {a}$일 때는, $(m^A, i^A)$는 $(a, 1)$이므로, $i_a^A = 1 \ge 2 \times 1 - 1$이고, $b \ne a$인 $b$에 대해서, $i_b^A = -1 \le 2 \times 0 -1$로 성립합니다.

이제 두 집합 $A$와 $B$를 합치는 경우를 생각합시다. 임의의 $A$, $B$, $v$에 대해서 다음이 성립합니다.

• $i^A_v + i^B_v \ge (2 \times {\rm freq}_A(v) - |A|) + (2 \times {\rm freq}_B(v) - |B|) = 2 \times freq_{A \cup B}(v) - |A \cup B|$.

이제 여러 경우를 나누어 봅시다.

• $m^A = m^B$인 경우, $i^{A \cup B}_v = i^A_v + i^B_v \ge 2 \times {\rm freq}_{A \cup B}(v) - |A \cup B|$입니다.
• $m^A \ne m^B$인 경우, 일반성을 잃지 않고, $i^A \ge i^B$라고 합시다.
  • $v \ne m^A$인 경우, $i^A_v < 0$임에 주목합니다. $i^{A \cup B}_v = -(i^A_v - i^B_v) \ge i^A_v + i^B_v$ 이고, $i^A_v + i^B_v \ge 2 \times {\rm freq}_{A \cup B}(v) - |A \cup B|$입니다.
  • $v = m^A$인 경우, $i^B_v<0$임에 주목합니다. $i^{A \cup B}_v = i^A_v - i^B_v \ge i^A_v + i^B_v$이고, $i^A_v + i^B_v \ge 2 \times {\rm freq}_{A \cup B}(v) - |A \cup B|$입니다.

그렇기 때문에, 귀납 명제와 본 명제가 성립합니다. $\square$

우리는 이를 이용해서 다음 알고리즘을 생각할 수 있습니다.

• 수열 $A$의 각 원소 $A_1, \cdots, A_N$에 대해서, 수열 $A'$을 $(A_1, 1), \cdots, (A_N, 1)$와 같이 구성합니다.
• 각 쿼리 $(i, j)$마다, 다음을 진행합니다.
  1. 수열 $A[i:j]$에 절반 초과로 등장하는 원소가 있는지 계산하고 싶을 때는, $A'_l, \cdots, A'_r$를 임의의 순서대로 $\oplus$한 연산의 결과를 가져옵니다.
  2. 해당 계산 결과의 $m$이 실제로 절반 초과로 등장하는지를 확인합니다.

1번 연산은 세그먼트 트리 등의 자료구조를 사용하면 $O(\log N)$시간에, 2번 연산은 정리 2의 참고를 사용해서 $O(\log N)$ 시간에 구할 수 있습니다. 결론적으로 다음과 같은 정리를 작성할 수 있습니다.

 

정리 5. 길이 $N$인 배열 $A$가 주어질 때, $A[i:j]$에서 절반 초과로 등장하는 원소가 있는지의 여부를 초기화 $O(N)$, 쿼리당 $O(\log N)$ 시간에 구할 수 있습니다. $\square$

일반적 경우를 효율적으로 해결하는 방법

일반적인 경우의 문제를 해결해보도록 합시다. 우리는 다음 정리를 증명할 것입니다.

 

정리 6. 크기 $N$의 배열과 고정된 $1$이상 $N$이하의 값 $k$에 대해, 구간 최빈값을 $O(N + (N/k)^2)$ 공간 및 초기화 $O(N^2/k)$, 쿼리당 $O(k)$ 시간에 구할 수 있습니다. $k = O(\sqrt N)$인 경우에, 구간 최빈값을 $O(N)$ 공간 및, 초기화 $O(N \sqrt N)$, 쿼리당 $O(\sqrt N)$에 해결할 수 있습니다.

 

정리 6의 증명.

우리는 크기 $k$의 블럭들로 구간들을 나눌 것입니다. $i$번째 블럭은 $A[ik+1: i(k+1)]$에 해당합니다. 이러면 블럭이 총 $\lceil N / k \rceil$ 개 생기고, $k$의 배수가 되도록 마지막 블럭을 적당한 방식으로 처리합니다(마지막 블럭에 대해 예외처리를 해도 좋고, 임의의 값으로 채워넣어도 좋습니다.)

임의의 구간 $A[i:j]$는 $b_i = \lceil (i-1) / k\rceil$부터 $b_j = \lfloor j/k \rfloor -1$번째 블럭을 온전히 포함합니다. 이 연속된 블럭을 몸통이라고 합시다. 이 연속된 블럭을 제외한 나머지 구간인 $A[i: \min(b_ik, j)]$와 $A[\max((b_j+1)k+1, i):j]$는 각각 머리와 꼬리라고 합시다. 머리, 꼬리, 몸통은 $1$개 이상이 비어있을 수도 있습니다.

보조정리 1'을 사용하면, $A[i:j]$의 최빈값은 몸통의 최빈값이거나, 머리의 원소이거나, 꼬리의 원소입니다. $b_i$번째부터 $b_j$번째 블럭의 최빈값을 $O(N + (N/k)^2)$의 공간과 $O(N^2/k)$의 시간을 써서 미리 초기화를 합시다. $i$ 번째 블럭에서 시작해서, 정리 1에 소개된 일반적인 최빈값 알고리즘을 사용하면 됩니다. 이제, 머리와 꼬리의 원소는 총 $2k$개 이하가 있기 때문에, 보조정리 2를 사용하면 $O(k \log N)$ 시간에 쿼리를 해결할 수 있습니다.

이 알고리즘을 자세히 살펴보면, 다음과 같습니다.

1. 최빈값 $x$, 최빈값이 등장하는 횟수 $m$을 $b_i$번째 블럭부터 $b_j$번째 블럭까지의 합으로 계산합니다.
2. 머리(와 꼬리)의 원소 $A[s]$에 대해서, 다음을 반복적으로 계산합니다.
   1. $A[i:j]$에서 $A[s]$가 등장하는 횟수가 $m$보다 크면, $x$를 $s$로, $m$을 $s$가 등장한 횟수로 바꿉니다.

우리는 보조정리 2에서, $A[l:r]$에 $v$가 몇 번 등장하는지를 구하는 쿼리당 $O(\log N)$ 알고리즘에 대해서 알아보았습니다. 이제 이 $O(\log N)$ 부분을 없애고 싶지만, 이 쿼리를 $O(1)$ 시간에 해결하기는 어려워 보입니다. 이제, 보조정리 2에서 사용하는 과정을 잘 살펴봅시다.

1. 값이 $v$인 수의 인덱스가 저장된 배열 $P_v$를 가져와서, $P_{v,x-1} < l \le P_{v, x}$인 $x$를 찾습니다.
2. $P_{v, y} \le r < P_{v, y+1}$을 구해서, $r-l$을 반환합니다.

여기서 우리는 각 과정을 최적화 할것입니다.

1. 우리는 사실, $A[i:j]$에서 임의의 값인 $v$가 등장하는 횟수를 찾는 게 아닌, $A[i]$가 등장하는 횟수를 찾는 것으로 충분합니다. 머리에서 $A[s]$가 처음으로 등장하는 경우, $A[s:j]$와 $A[i:j]$에서 $A[s]$가 등장하는 횟수는 동일합니다. $P_{A[i], x} = i$ 인 $x$를 미리 계산해서 저장해 놓을 수 있습니다.
2. 우리는 사실, $A[i:j]$에서 $A[i]$가 등장하는 횟수를 찾는게 아닌, $m$ 이상인지의 여부만 찾으면 됩니다. $P_{v, x+m}$이 $r$ 이하인지 확인해 보는 것으로 대신할 수 있습니다.

각 과정은 모두 $O(1)$에 계산할 수 있기 때문에, 우리는 다음과 같은 방법으로 문제를 해결할 수 있습니다:

전처리

1. 블럭 크기 $k$와 블럭 개수 $s = \lceil N/k \rceil$을 정합니다. $i$번째 블럭부터 $j$번째 블럭까지의 최빈값과, 최빈값이 등장하는 횟수를 담는 배열 $F[i,j]$를 만듭니다.
2. 시작하는 블럭의 위치인 $i = 0, \cdots, s-1$에 대해서 다음을 반복합니다.
   1. 수가 등장한 횟수를 담는 배열 $cnt$를 만들어서 $0$으로 초기화합니다.
   2. 최빈값 $v$를 임의의 값 $*$로, 최빈값이 등장한 횟수 $m$을 $0$으로 초기화합니다.
   3. $idx = ki+1, \cdots, N$에 대해 다음을 반복합니다.
      1. $cnt[A[idx]]$를 $1$ 증가시킨 후, $m$보다 큰 경우 $(v, m)$을 $(A[idx], cnt[A[idx]]+1)$로 바꿉니다.
      2. $idx$가 $kj$꼴일 경우, $F[i, j]$에 $(v, m)$을 저장합니다.
3. 원소가 배열인 크기 $N$의 배열 $P$를 만듭니다.
4. 인덱스 $i=1, \cdots, N$에 대해서, $P_{A[i]}$에 $i$를 삽입합니다. 그리고, 그때의 $P_{A[i]}$의 길이를 $P^{-1}[i]$에 저장해, $P_{A[i]}[P^{-1}[i]]$가 $i$가 되도록 합니다.

해당 전처리는 $O(N^2/k)$ 시간이 걸리고, 만들어지는 배열의 크기는 $O(N + (N/k)^2)$입니다.

쿼리

1. $A[i:j]$의 최빈값과 등장 횟수를 묻는 쿼리가 주어집니다.
2. $b_i = \lceil (i-1) / k\rceil$, $b_j = \lfloor j/k \rfloor -1$를 구합니다.
3. $b_i \le b_j$ 인 경우, $(m, v)$를 $F[b_i, b_j]$로, $b_i > b_j$인 경우 $(m, v)$를 $(*, 0)$으로 초기화합니다.
4. $s = i, i+1, \cdots, \min(b_ik, j)$에 대해, 다음을 반복합니다.
   1. $l$을 $P^{-1}[s]$로 구합니다. $l > 1$이고, $P_{A[s]}[l-1] \ge i$ 인 경우, 이미 $A[s]$를 확인 했으므로, 다음 $s$로 넘어갑니다.
   2. $r = l + v$를 계산합니다. $r > |P_{A[s]}|$이거나, $P_{A[s]}[r] > j$인 경우, $A[s]$는 $A[i:j]$에서 $v$번 이하로 등장하므로, 다음 $s$로 넘어갑니다.
   3. $r \le |P_{A[s]}|$이고, $P_{A[s]}[r] \le j$인 동안 $r$을 증가시킵니다.
   4. $(m, v)$를 $(A[s], r-l)$로 바꿉니다.
5. $b_i \le b_j+1$인 경우 (즉, 꼬리가 존재하는 경우), $s = j, j-1, \cdots, \max((b_j+1)k+1, i)$에 대해, 다음을 반복합니다.
   1. $r$을 $P^{-1}[s]$로 구합니다. $r < |P_{A[s]}|$이고, $P_{A[s]}[r+1] \le j$인 경우, 이미 $A[s]$를 확인 했으므로, 다음 $s$로 넘어갑니다.
   2. $l = r - v$를 계산합니다. $l < 1$이거나, $P_{A[s]}[l] < i$인 경우, $A[s]$는 $A[i:j]$에서 $v$번 이하로 등장하므로, 다음 $s$로 넘어갑니다.
   3. $l \ge 1$이고, $P_{A[s]}[l] \ge i$인 동안 $l$을 증가시킵니다.
   4. $(m, v)$를 $(A[s], r-l)$로 바꿉니다.
6. $A[i:j]$의 최빈값은 $m$, 등장 횟수는 $v$입니다.

여기서 나머지 과정은 전부 시간 복잡도가 자명하지만, 4-3, 5-3번 과정이 자명하지 않습니다. 관찰할 수 있는 점은, $A[i:j]$의 최빈값의 등장 횟수는, $F[b_i, b_j]$의 $v$와 $2k$ 이하로 차이가 나며, 해당 4-3, 5-3 과정은 $v$를 무조건 $1$씩 증가시키기 때문에, 총 $2k$번 이하로 실행됩니다.

총 시간 복잡도는 $O(k)$가 됩니다. $\square$

시간 복잡도 하한

우리는 $\sqrt{N} \times \sqrt{N}$ 크기 행렬의 boolean 곱셈 문제를 살펴봅시다. 행렬 곱셈에서, 곱셈이 $\wedge$연산, 덧셈이 $\vee$연산으로 바뀐 것입니다.

• 두 행렬 $A$, $B$와 행렬의 곱 $C = A \times B$에 $C_{ij} = 1$인 것은, $A_{ik} = B_{kj} = 1$인 $k$가 존재한다는 것과 동치입니다.

이 문제는 행렬 곱셈을 사용하면 $\tilde O(N^w)$에 해결 가능합니다. 구체적으로는, Coppersmith-Winograd의 $O(N^w)$ 행렬 곱셈 알고리즘에서, 각 수를 $N+1$ 이상의 소수 $p$로 나눈 나머지를 다루는 체인 $\mathbb{Z}_{p}$에서 관리합니다. 이 경우에 일반적인 행렬 곱을 구하고, (일반적인 정수에서 계산된) $C$의 각 원소는 $0$ 이상 $N$ 이하일 것이기 때문에 $\mathbb{Z}_{p}$에서 계산한 결과와 같으며, 각 행렬 성분이 $1$ 이상인지의 여부를 확인해 주면 됩니다.

하지만, 우리는 "조합론적인" $\tilde O(N^3)$ 보다 빠른 풀이를 찾지 못했습니다. 여기서 "조합론적인" 이라는 말의 정의는 매우 애매하지만, 흔히 다음과 같은 조건을 만족하는 것을 조합론적이라고 합니다.

• 뺄셈을 사용하지 않습니다.
• 현실적으로 구현 가능한 가벼운 연산들을 사용합니다.

$O(N^3 / \log^2N)$과 같은 빠른 풀이는 Method of Four Russian 같은 방법이 있고, 이 글에서는 따로 설명하지 않습니다. 이 방식도 $O(N^{3-\epsilon})$을 달성하지는 못했습니다.

이제 다음 명제를 증명합시다.

 

정리 7. 크기 $N$인 배열의 구간 최빈값을 전처리 $O(p(n))$, 쿼리당 $O(q(n))$에 구할 수 있으면, $\sqrt{N} \times \sqrt{N}$ 크기 행렬 곱셈을 $O(p(N) + N \cdot q(N) + N)$ 시간에 할 수 있습니다.

 

우리는 다음과 같은 관찰을 사용합니다.

관찰 1. $S$를 각 원소가 전체집합 $U$에 속해 있는 multiset이라고 합시다. $U$의 각 원소를 $S$에 하나씩 추가하면, 최빈값이 등장하는 횟수는 $1$ 증가합니다.

관찰 2. $A$, $B$를 두 (중복을 허용하지 않는) 집합이라고 합시다. $S$를 $A$와 $B$의 (multiset) 합집합이라고 합시다. $A \cap B = \phi$일 경우, $S$의 최빈값은 $1$번, $A \cap B \ne \phi$일 경우 $S$의 최빈값은 $2$번 등장합니다.

 

정리 7의 증명. $A$와 $B$의 boolean 곱셈은, $A$의 $i$번째 행에서 $1$이 들어있는 인덱스의 집합 $A_i$, $B$의 $j$번째 열에서 $1$이 들어있는 인덱스의 집합 $B_j$에 대해, $A_i \cap B_j = \phi$인지 아닌지 확인하는 문제입니다. 크기 $2N$의 배열을 만드는데, 왼쪽 절반은 $A$에 대한 정보, 오른쪽 절반은 $B$에 대한 정보를 저장합시다.

행렬을 원소가 $\sqrt{N}$ 개 들어있는 $2 \sqrt{N}$개의 블럭으로 나눕시다. 왼쪽에서 $i$번째 블럭에 차례로 집합 $A_i$와, $\{1, 2, \cdots, \sqrt{N}\} \setminus A_i$의 원소를 기록합시다. 가운데를 기준으로 오른쪽에서 $j$번째 블럭에는 차례로 $B_j$와 $\{1, 2, \cdots, \sqrt{N}\} \setminus B_j$의 원소를 기록합시다.

왼쪽에서 $i-1$번째 블럭, 오른쪽에서 $j-1$번째 블럭 사이에는 총 $\{1, 2, \cdots, \sqrt{N}\}$이 $i+j-2$개 있고, 왼쪽에서 $i$번째 블럭의 첫 (오른쪽) $|A_i|$개의 원소와 $j$번째 블럭의 첫 (왼쪽) $|B_j|$개의 원소를 포함해서 쿼리를 합니다. 최빈값의 빈도가 $i+j$인 경우, $A_i$와 $B_j$의 교집합이 있고, $i+j-1$인 경우, 교집합이 없습니다. 이 방법으로 $C_{i j}$를 한 번의 쿼리로 알 수 있고, 총 쿼리를 $N$번 하는 것으로, 배열 $C$를 구합니다. $\square$

결론적으로, 길이 O(N)의 배열에서 쿼리 O(N) 개를 한 번에 $O(N^{1.5 - \epsilon})$에 답하기는 힘들어 보입니다.

구현

다음은 C++11로 구현된 최빈값을 구하는 Mode class입니다. 생성자로는 std::vector<T> A를 받으며, T가 비교 가능한 타입이어야 합니다. 초기화에 $O(N \sqrt{N})$, 쿼리당 $O(\sqrt{N})$시간에 최빈값을 계산합니다. query(i, j)는 $0$-index 배열 $A$의 $i$ 이상 $j$ 미만의 인덱스에 해당하는 최빈값과 최빈값이 등장하는 빈도를 차례로 std::pair로 반환합니다.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

template <typename T>
class Mode
{
public:
    // Initializes Mode query
    Mode(vector<T> _A) : N(_A.size()), D(_A.begin(), _A.end()), A(N)
    {
        if (_A.empty())
            return;
        sort(D.begin(), D.end());
        D.erase(unique(D.begin(), D.end()), D.end());
        for (int i = 0; i < N; i++)
            A[i] = distance(D.begin(), lower_bound(D.begin(), D.end(), _A[i]));

        M = D.size();
        K = sqrt(N);
        S = (N + K - 1) / K;
        F.resize(S);
        for (int i = 0; i < S; i++)
            F[i].resize(S);

        for (int i = 0; i < S; i++)
        {
            vector<int> cnt(M);
            int v = -1, m = 0;
            for (int j = i; j < S; j++)
            {
                for (int k = K * j; k < min(N, K * (j + 1)); k++)
                    if (++cnt[A[k]] > m)
                        v = A[k], m++;
                F[i][j] = {v, m};
            }
        }

        P.resize(M);
        Pinv.resize(N);
        for (int i = 0; i < N; i++)
        {
            Pinv[i] = P[A[i]].size();
            P[A[i]].push_back(i);
        }
    }

    // Calculate mode of A[i:j), where 0 <= i < j < N
    pair<T, int> query(int i, int j)
    {
        int bi = (i + K - 1) / K, bj = j / K - 1;
        int m = -1, v = 0;
        if (bi <= bj)
            tie(m, v) = F[bi][bj];

        for (int s = i; s <= min(bi * K, j) - 1; s++)
        {
            int l = Pinv[s];
            if (l - 1 >= 0 && P[A[s]][l - 1] >= i)
                continue;
            int r = l + v;
            if (r >= (int)P[A[s]].size() || P[A[s]][r] >= j)
                continue;
            do
            {
                r++;
            } while (r < (int)P[A[s]].size() && P[A[s]][r] < j);
            m = A[s];
            v = r - l;
        }
        if (bi <= bj + 1)
            for (int s = j - 1; s >= (bj + 1) * K; s--)
            {
                int r = Pinv[s];
                if (r + 1 < (int)P[A[s]].size() && P[A[s]][r + 1] < j)
                    continue;
                int l = r - v;
                if (l < 0 || P[A[s]][l] < i)
                    continue;
                do
                {
                    l--;
                } while (l >= 0 && P[A[s]][l] >= i);
                m = A[s];
                v = r - l;
            }
        return {D[m], v};
    }

private:
    int N, M, K, S;
    vector<T> D;
    vector<int> A;
    vector<vector<pair<int, int>>> F;
    vector<vector<int>> P;
    vector<int> Pinv;
};​

참고 문헌

• Linear-Space Data Structures for Range Mode Query in Arrays, Timothy M. Chan et, al.
• Boyer, R. S., & Moore, J. S. (1991). MJRTY—a fast majority vote algorithm. In Automated Reasoning (pp. 105-117)