Posting

Machbase의 최신 소식을 지금 만나보세요

[MACHBASE 이야기] Range Minimum Query와 Segment Tree

마크베이스 선임연구원 송규욱

이번 포스트에서는 Range Minimum Query와 Segment Tree에 대해서 알아보고자 한다.
Range Minimum Query (aka RMQ) 문제는 Computer Science 분야에서 많이 연구되는 문제로서, 현실 세계에서도 적용가능한 경우가 많다.
예를들어, “2001년부터 2010년 사이에 최저기온을 기록한 날은 언제인가?” 와 같은 질의도 RMQ 문제로 표현될 수 있다.
Range Minimum Query에 대한 정의를 알아보고 그에 대한 솔루션중에 하나인 Segment Tree에 대해서 자세히 알아보자.

Range Minimum Query

Range Minimum Query (RMQ) 는 비교 정렬이 가능한 값을 담고있는 임의의 배열이 주어졌을때, 배열의 특정범위(sub-array)에서 최소값이 있는 index를 찾는 문제이다.
예를들어 integer 값을 갖고있는 배열 A[0, N-1] 에서,

RMQA(l,r) = arg min(A[k]) (with l <= k <= r)  즉, A[l, r] 에서 최소값이 존재하는 곳의 위치를 반환한다. Example: 배열 A[0, N-1]가 아래와 같이 주어졌을때, RMQ를 구하는 예이다.

주어진 범위에서 가장 작은 값은 A[3] 이므로 RMQA(2,7) 의 결과는 3이 된다.

Trivial Solution

모든 RMQ 질의에 대해서 loop를 돌며 배열의 값을 확인하는 방법이다.

int RMQ(int A[MAXN], int L, int R)
{
    int i, found;
    found = L;
    for (i = L+1; i <= R; i++) {
        if (A[i] < A[found])
            found = i;
    }
    return found;
}

각 질의에 대해 O(N)의 시간 복잡도를 갖는다. 간단하지만 배열의 크기가 큰 경우 시간이 오래걸리므로 사용하기 힘들다.

Solution 2: Precalculation

주어진 배열 A에 대해 미리 전처리를 수행하여 결과를 저장해 놓는 방법이다.

R(i, j)는 구간 [i,j] 에 대한 RMQ 값을 갖고있다고 가정한다. (단, i <=j 이고 0 <= i, j <= N-1)
그렇다면 우리는 다음과 같은 recurrence relation을 세울 수 있다.

  • R(i, i) = i (구간의 길이가 1이므로 자기 자신이 된다)
  • R(i, j) = j (A[j]가 A[R(i, j-1)] 보다 작은경우) or
                 R(i, j-1) (그렇지 않은 경우)

따라서, Dynamic Programming 기법을 적용하여 아래와 같이 구현할 수 있다. O(N^2) 시간 복잡도를 갖는다.

void process(int R[MAXN][MAXN], int A[MAXN], int N)
{
    int i, j;
    for (i = 0; i < N; i++) {
        R[i][i] = i;
    } 
    for (i = 0; i < N; i++) {
        for (j = i + 1; j < N; j++) {
            if (A[R[i][j-1]] < A[j])
                R[i][j] = R[i][j-1];
            else
                R[i][j] = j;
        }   
    }
}

j >= i 를 만족하는 모든 (i, j) 에 대해 R[i][j] 는 RMQ(i, j) 의 결과를 가지고 있다. 따라서 질의가 들어오면 O(1) 시간복잡도 안에 결과를 반환할 수 있다.
하지만 O(N^2) 의 공간 복잡도를 가지므로 메모리를 많이 사용하게 되고, 배열 A가 자주 업데이트 되는 상황에서는 사용이 불가능하다.

Segment Tree

RMQ 문제를 해결할 수 있는 효과적인 방법중에 하나로 Segment Tree가 있다.
Segment Tree는 구간의 대표값을 tree 형태로 저장하는 자료구조이다.

Tree Construction

RMQ 문제를 해결하기 위해 다음과 같이 재귀적 방법으로 tree를 구성해보자.

  • Root node는 [0, N-1] 구간에서의 RMQ 결과를 갖는다.
  • 구간 [i, j]에 대한 node는 [i, (i+j)/2] 구간에 대한 node를 왼쪽 자식으로, [(i+j)/2+1, j] 구간에 대한 node를 오른쪽 자식으로 갖는다.

Example:

배열 A[0,9] = [2, 4, 3, 1, 6, 7, 8, 9, 1, 7] 에 대한 Segment Tree를 구성해보자.

Query

질의가 들어올 경우 root node에서 시작하여 재귀적인 방법으로 탐색을 한다.

  • 해당 node의 범위가 질의 범위에 해당하지 않는 경우 곧바로 return 한다.
  • 해당 node의 범위가 질의 범위에 완전히 속하는 경우 node가 가지고 있는 값을 return 한다.
  • 그 이외의 경우 자식 node를 호출한 후 결과중 값이 작은쪽을 return 한다.

Example:

위에 구성된 tree를 이용하여 RMQA(2,7)을 구하는 과정을 살펴보자.

Update

배열 A에 update가 발생할 경우 tree도 같이 update를 해 주어야 한다.
자신의 index가 해당하는 구간의 node로 traverse 한 후 leaf node를 update 해주고, 이를 부모 node에 반영한다.

Example:

위에 주어진 배열 A에 대해 A[7] = 2 로 update 한 경우

구현

Segment Tree의 구현은 배열을 이용하여 할 수 있다.

  • Root node를 1번 index로 정한다.
  • Node의 index가 x 인 경우, left child 는 x*2, right child 는 x*2+1 이 된다.

배열 A의 크기가 N 인 경우 tree의 높이가 ceil(log2(N))이 됨을 감안하여 Tree[2*2^ceil(log2(N))] 만큼 공간을 사용하게 된다.

int init(int node, int L, int R, int tree[MAXIND], int A[MAXN], int N)
{
    int left, right;
    if (L == R)
        tree[node] = L;
    else {
        left  = init(2*node, L, (L+R)/2, tree, A, N);
        right = init(2*node+1, (L+R)/2+1, R, tree, A, N);
        if (A[left] <= A[right])
            tree[node] = left
        else
            tree[node] = right;
    }  
    return tree[node];
}

int query(int node, int L, int R, int tree[MAXIND], int A[MAXN], int i, int j)
{
    int left, right;
    if (L > j || R < i)
        return -1;
    if (L >= i && R <= j)
        return tree[node];
    left = query(2*node, b, (L+R)/2, tree, A, i, j);
    right = query(2*node+1, (L+R)/2+1, R, tree, A, i, j);
    if (left == -1)
        return right;
    if (right == -1)
        return left;
    return A[left] < A[right] ? left : right;
}  

int update(int node, int L, int R, int tree[MAXIND], int A[MAXN], int u)
{
    int left, right;
    if (u < L || u > R)
        return tree[node];
    if (L == R)
        tree[node] = L;
    left = update(2*node, L, (L+R)/2, tree, A, u);
    right = update(2*node+1, (L+R)/2+1, R, tree, A, u);
    return tree[node] = A[left] < A[right] ? left : right;
}

시간복잡도

Tree node의 개수는 2*N-1 이고 각 node는 tree 구축 시 최대 한번만 사용된다. 따라서 tree 구축에 대한 시간복잡도는 O(N)이 된다.
Query의 경우 각각의 tree level에 대해 최대 4개의 node를 방문한다. 따라서 tree level에 따라 복잡도가 결정되므로 O(log(N))이 된다.
Update 또한 마찬가지로 level 당 최대 하나의 node를 방문하므로 O(log(N))이 된다.

Proof

위 그림에서 첫번째 경우가 하나의 level에서 4개의 node를 방문해야 하는 경우이다.
하지만 범위를 G까지 넓히면 [E, F]가 완전히 포함되므로 E, F를 방문하는 대신 B에서 pruning이 되므로 오히려 방문 node 개수가 줄어들게 된다.
따라서, 범위가 어떻게 들어오더라도 같은 level에서 4개보다 많은 node를 탐색하는 경우가 없음을 알 수 있다.

연관 포스트

C언어로 Binary data를 Machbase에 넣기

1.개요 Data를 다루다 보면 numeric, varchar 형 데이터뿐만 아니라 JPG, PNG, MP3와 같은 Binary data도 database에 저장해야 할 때가 존재한다. 그러나 일반 data들과는 달리 Binary

[MACHBASE 연동] Android studio에서 JDBC 연결하기

마크베이스 기술지원본부 이현민 1. 개요 수많은 데이터들이 많은 환경에서 생성되고 있는 오늘날, 우리 현대인들의 동반자인 스마트폰 또한 데이터생성의 주체로써 또는 전달자로서 알게 모르게 그 구실을