[Algorithm] RMQ (Range Minimum Query)

RMQ는 어떤 배열이 존재할 때 특정 범위의 가장 작은 값을 구할 때 사용하는 자료구조이다.

 

다음과 같은 배열이 있다고 하자.

 

RMQ (1, 5)의 의미는 Arr[1] 부터 Arr[5] 까지의 값 중 가장 작은 값을 의미한다. 위 배열의 경우 "3"이 된다.

 

이 RMQ를 구하는 방법에는 여러가지가 있지만 그 중 전처리 과정의 시간 복잡도가 O(N*log N)이고 원하는 값을 얻을 때의 시간 복잡도가 O(1)인 방법을 공부해보려고 한다.

 

RMQ 전처리 과정

 

우선 길이가 1인 RMQ를 구한다. RMQ (0, 0), RMQ (1, 1), RMQ(2, 2) ... RMQ(N, N)을 모두 구하는 것이다.

 

길이가 1이기 때문에 당연하게도 RMQ(i, i)의 값은 arr[ i ]의 값과 똑같을 것이다.

 

그 다음 길이가 2인 RMQ를 구한다. RMQ (0, 1), RMQ (1, 2), RMQ(2, 3) ... RMQ(N-1, N)을 모두 구하는 것이다.

 

RMQ(i, i+1)을 구한다고 하면 미리 구해놓은 길이가 1인 RMQ를 이용하면 된다.

 

RMQ(i, i)와 RMQ(i+1, i+1) 중 작은 값이 RMQ(i, i+1)의 값이 된다.

 

그 다음 길이가 4인 RMQ를 구한다. RMQ (0, 3), RMQ (1, 4), RMQ(2, 5) ... RMQ(N-3, N)을 모두 구하는 것이다.

 

RMQ(i, i+3)을 구한다고 하면 미리 구해놓은 길이가 2인 RMQ를 이용하면 된다.

 

RMQ(i, i+1)와 RMQ(i+2, i+3) 중 작은 값이 RMQ(i, i+3)의 값이 된다.

.

.

.

이런 식으로 길이가 2의 거듭제곱 꼴로 늘어나 RMQ를 모두 구해놓는다.

 

거듭제곰 꼴로 늘어나기 때문에 RMQ를 구하는 시간 복잡도는 O(N*log N)이다.

 

원하는 값 구하기

전처리 과정을 거치고 나서 원하는 값을 구할 때는 O(1), 즉 상수 시간 안에 구할 수가 있다.

 

가장 먼저 구하려는 범위의 길이를 알아야 한다.

 

예를 들어 RMQ(1, 5)를 구하려고 한다면 이 길이가 5라는 것을 확인한다.

 

길이가 N이라고 한다면 N보다 같거나 작은 수 중에서 가장 큰 2의 거듭 제곱을 구한다.

 

길이가 5인 경우 4가 될테고 길이가 21인 경우 16이 될 것이다.

 

2의 거듭 제곱을 구하는 이유는 우리가 RMQ를 구할 때 길이가 2의 거듭 제곱 꼴인 배열을 기준으로 구했기 때문이다.

 

만약 RMQ(1, 4)와 같이 길이가 4, 즉 2의 거듭 제곱 꼴이라면 우리가 미리 구해놓았기 때문에 바로 구할 수 있다.

 

그러나 RMQ(1, 5)와 같이 길이가 5, 즉 2의 거듭 제곱 꼴이 아니라면 우리가 미리 구해놓지 않았기 때문에 추가적인 연산을 해야 한다.

 

아래 배열에서 RMQ(1, 5)를 구한다고 해보자.

 

우리는 길이가 5인 RMQ를 구하지 않았지만 길이가 4인 RMQ를 알고 있다.

 

그러면 답은 간단하다 RMQ(1, 4)와 RMQ(2, 5) 중 작은 값이 RMQ (1, 5)가 될 것이다.

Min(RMQ(1, 4), RMQ(2, 5))를 구하면 되고 이 역시 시간 복잡도는 상수 시간이다.