Algorithm: RMQ(Range Minimum Query)

RMQ란 배열에서 일부 구간을 선택하여 그 구간에서의 최소값을 찾는 알고리즘이다.

RMQ를 해결함에 있어서 여러 방법이 존제하는데 살펴보자.

 

• Brute-force Method
  • 이 방법은 가장 단순한 방법으로 해당 구간 내에 모든 원소를 비교하는 방법이다. 
  • 각 쿼리가 주어질때마다 해당 구간에서 최소값을 찾기 위해 O(n) 시간이 소요된다
  • 이 방법은 구현이 간단하고 쿼리가 적은 경우에는 유용할 수 있지만 보통은 그렇지 않다
• 전처리: O(n^2), 질의: O(1)
  • 가능한 a, b 모두에 대해 미리 답을 다른 배열 B[a][b]에 미리 답을 저장해 두는 방법이다. 
  • 값이 변하지만 않는다면 유용하지만 그렇지 못할경우 비효율적
• 전처리: O(n), 질의 O(sqrt(n))
  • 이 방법은 square root decomposition을 이용하는 방법이다. 
  • 배열을 일정한 크기의 블록으로 분할하고 각 블록에 대한 최소값을 미리 계산하여 저장하는 방식을 사용한다.
  • 쿼리할 구간이 블록의 범위를 벗어난다면 내부의 값들과 비교하며 최소값을 찾고, 블록에 포함된 경우는 저장된 값을 출력하면 된다. 
  • 알고리즘의 동작과정은 다음과 같다
    • 블록 크기를 정한다. 일반적으로 sqrt(n)
    • 블록 내에서 최소값을 저장할 배열 초기화
    • 블록 내에서의 최소값을 구하고 저장 --> 모든 블록에 대해 동일
    • 구간 [a,b] 에 대한 쿼리 발생시 a와 b가 속한 블록을 찾는다
      • a, b가 같은 블록에 속할경우, 해당 블록 내에서 a부터 b까지의 최소값을 직접 계산한다.
      • 다른 블록에 속할 경우 첫 블록부터 a 블록 끝까지, 마지막 블록에서 R까지의 부분 구간 최소값을 구하고 중간 블록들에 대해서는 미리 저장된 최소값을 계산
    • ex) 배열 A[4,2,1,5,6,9,11,0,4,2,33,12,52,9,17,13] 에 대해 [2,9] 구간의 RMQ
      • 배열의 블록을 나눈다 (sqrt(len(A)) = 4)
        • Block 1: [4,2,1,5]
        • Block 2: [6,9,11,0]
        • Block 3: [4,2,33,12]
        • Block 4: [52,9,17,13]
      • 각 블록의 최소값을 계산한다
        • Block 1: 1
        • Block 2: 0
        • Block 3: 2
        • Block 4: 9
      • 구간 [2,9]에서 최소값을 구하기 위해 해당 구간이 포함된 블록들을 찾는다
        • Block 1: [2,5], 가 포함되므로 Block 1의 최솟값 1과 비교
        • Block 2: [6,9], 가 포함되므로 Block 2의 최솟값 0과 비교
        • Block 3: [10, 13], 이 포함되므로 Block 3의 최솟값 2 와 비교
        • Block 4: 포함되지 않으므로 비교하지 않음
      • 각 블록에서 미리 계산해둔 최소값을 이용하여 해당 구간에서의 최소값 계산
        • [2,5] : 1
        • [6:9] : 0
        • [10,13] : 2
      • 최소값중 가장 작은 값을 선택하여 반환 (0 반환)
• 전처리: O(n log n), 질의: O(1)
  • 이 방법은 Sparse Table 을 구성하여 해결한다
  • 이 방법은 각 a[i] 마다 RMQ(i,i+1), RMQ(i,i+2),..를 미리 구해 놓는 방법이다
  • 구해야 할 정답의 수는 최대 n log n 개
    • 왜일까?
      • 예를 들어 RMQ(i, i+4) 를 구할때, a[i], ... , a[i+4] 를 모두 구하는 것이 아닌, RMQ(i, i+1) 과 RMQ(i+3, i+4)만 비교하면 되기 때문이다
  • 동작과정
    • ST[i][i] = i 로 초기화 한다
    • 구간 길이가 2^k인 구간에 대해 최소값을 계산 (단 k는 log(n) 이하의 자연수)
    • 구간 길이가 2^k인 구간에 대해 인접한 두 구간의 최소값을 계산하여 저장한다
      • ST[i][i + 2^(k-1)] = min ( ST[i][i + 2^(k-1)-1], ST[i + 2^(k-1)][i + 2^(k-1)]
      • 여기서 [i, i+2^(k-1)]란, 배열의 인덱스 i 부터 i+2^(k-1) 까지의 구간이다
    • 예를 들어 배열 A = [3, 1, 4, 2, 6, 7, 8, 5] 의 배열이 있다고 치자. 다음은 배열 A의 ST 배열이다
    •  

구간	1	2	3	4	5	6	7	8
3	3	1	1	1	1	1	1	1
1		1	1	1	1	1	1
4			4	2	2	2	2
2				2	2	2	2
6					6	6	5
7						7	5
8							5