[자료구조] 희소 배열 (Sparse Table)의 구현(JAVA)

언제 사용하는가

 

희소배열은 최소 범위 쿼리(Range Minimum Query)의 연산을 수행시 짧은 구현과 빠른 속도로

처리 하고 싶을때 사용하는 자료구조이다.

 

먼저 최소 범위 쿼리부터 알아보도록 하자.

 

https://en.wikipedia.org/wiki/Range_minimum_query

Range minimum query - Wikipedia

 

위키에서 보면 비교가능한 개체 배열에서 최소값을 찾는것을 말한다.

 

즉 이미 값이 정해져 있으며, 데이터의 삽입 삭제등의 연산이 없는 정적인 데이터에서

서로 연관관계가 있다면 원하는 쿼리를 수행하고 싶을때 희소 배열을 사용하면 효과적이란 의미이다.

 

https://brilliant.org/wiki/sparse-table/

Sparse Table | Brilliant Math & Science Wiki

 

이런 희소배열은 문자열에서 가장 긴 접두사 찾기, 최소 공통 조상등에서 활용도가 높다.

 

 

왜 효과적인가

 

간단한 예시를 들어 희소배열이 효과적인 이유를 설명해보도록 하겠다.

 

먼저 앞서 설명했듯 최소범위쿼리를 빠르게 수행할수 있게 해주는 자료구조이므로

최소범위쿼리를 사용하는 예시를 들어보겠다.

 

먼저 다음과 같은 그래프가 있다고 가정해 보도록 하겠다.

 

 

 

각 정점에서는 다른 정점을 가리키는 유일한 간선이 존재하고,

정점을 따라가다보면 사이클이 발생해 무한히 탐색하는 모양의 그래프임을 알 수 있다.

이때 어떤 정점 A에서 n번 이동했을때의 정점을 찾는 쿼리가 주어진다면,

그동안 공부했던 방법을 생각했을때 DFS를 사용한다면 찾을수 있지만 n이 커질수록

깊이가 깊어져 탐색시간이 O(N)이 걸린다는 것을 알 수 있다.

 

이럴때 희소배열을 사용한다면 이런 탐색시간을 O(logN)으로 줄여 효과적인 방법으로 

해당 노드를 찾아 낼 수 있다.

 

그렇다면 희소배열은 어떤식으로 사용하길래 이렇게 효과적으로 탐색시간을 줄일수 있는것인가

 

 

희소배열의 사용

 

희소배열은 우선 동적프로그래밍 기법을 응용한 하나의 자료구조이다.

 

먼저 각정점에서 한번만을 이동했을때의 결과를 표로 나타낸다면 다음 표와 같다.

 

A	1	2	3	4	5	6	7	8	9	10
n = 1	3	1	4	8	2	5	4	2	5	6

 

그리고 2번씩 이동했을때의 결과를 그림으로 표현한다면 다음 그림과 같다.

 

 

모양새가 썩 좋진 않다. 

이때 결과를 표로 이어서 표현한다면 다음과 같다.

 

A	1	2	3	4	5	6	7	8	9	10
n = 1	3	1	4	8	2	5	4	2	5	6
n = 2	4	3	8	2	1	2	8	1	2	5

 

 

이때 결과를 잘 보면 임의의 정점 A에서 n번 이동했을때의 결과인 정점 B에서 n번 이동했을때의 노드가

임의의 정점 A에서 2n번 이동했을때의 결과임을 알 수 있다.

 

이런 규칙을 사용해 n이 4일때의 노드를 찾고 싶다면 임의의 정점 A에서 2번 이동한 결과인

B정점에서 2번 이동한 정점을 찾으면되는것이다.

 

즉 단순 탐색을 통해 4번의 탐색을 찾을 필요 없이 2번의 이동만으로 4번탐색한 결과와 동일한 결과를

얻을수 있음을 알 수 있다.

 

이를 n = 8일때까지 표로 표현한다면 다음과 같다.

 

A	1	2	3	4	5	6	7	8	9	10
n = 1	3	1	4	8	2	5	4	2	5	6
n = 2	4	3	8	2	1	2	8	1	2	5
n = 4	2	8	1	3	4	3	1	4	3	1
n = 8	8	4	2	1	3	1	2	3	1	2

 

그럼 n = 5일때 즉 임의의 정점 A에서 5회 이동한 결과를 알고 싶다면 어떤식으로 찾으면 되는가

 

간단하다 임의의 정점 A에서 4번 이동한 결과인 n = 4인 노드에서 n = 1 인 노드를 찾으면된다.

즉 A가 1이라고 가정하면 4번 이동한 결과인 2번 노드에서 n = 1인 노드인 1이 바로 

1에서 5번 이동한 노드인 1을 찾을수 있는것이다.

 

이 부분만 그림으로 표현 하면 다음과 같다.

 

 

이런 방식으로 2^i 번의 횟수를 저장해 찾는 방식으로 희소배열을 구성해 원하는 값을

금방 찾아낼수 있는것이다.

 

물론 단순 탐색인 DFS와 비교해 메모이제이션을 사용하는 DP방식인 희소배열은

조금 더 메모리를 사용하는 방식이긴 하지만 n이 커질수록

압도적인 시간차이를 가져오기 때문에 효과적인 방법이라고 볼수 있다.

 

그럼 바로 자바소스로 구현해보도록 하겠다.

 

구현

 

먼저 필드로 각노드가 가리키는 유일한 노드를 갖는 데이터를 갖고 시작하도록 하겠다.

그리고 희소배열을 의미하는 필드와 노드의 개수 n, 이동할 횟수 h를 선언한다.

 

public class SparseTable {

    private final List<Integer> parents;
    private int[][] table;
    private int n, h;
}

 

각 노드가 가리키는 유일한 노드 데이터, 노드의 개수, 이동할 최대 횟수는 생성자를 통해 주입받고

초기화 해주도록 하겠다.

 

이때 이동할 최대 횟수는 2^i 번 이내 이므로 상용로그의 연산을 통해 간단히 구할 수 있다.

 

    public SparseTable(final List<Integer> parents, int n, int h) {
        this.parents = parents;
        this.n = n;
        this.h = getLog(h);
        table = new int[this.h + 1][n + 1];
    }

    private int getLog(int maxHeight) {
        return (int) Math.ceil(Math.log(maxHeight) / Math.log(2)) + 1;
    }

 

 

이어서 바로 희소배열을 구현해보도록 하겠다.

먼저 n = 1일때 즉 한번만 이동했을때의 결과를 저장해주도록 한다.

 

    public void setTable() { // 1부터 시작한다고 가정.
        for(int i = 1; i <= n; i++) {
            table[0][i] = parents.get(i);
        }

    }

 

i는 노드를 의미하는데 1번 노드부터 존재한다고 가정하고 1부터 차례로 노드를 저장해주도록 하겠다.

 

이어서 임의의 노드 A에서 n번 이동한 결과인 A에서 n/2번 이동한 결과인 B에서 n/2번 이동한 결과를

차례로 저장해주도록 하겠다.

 

앞서 설명했던 표의 흐름을 그대로 저장한다고 생각하면 되겠다.

 

    public void setTable() { // 1부터 시작한다고 가정.
        for(int i = 1; i <= n; i++) {
            table[0][i] = parents.get(i);
        }
        for(int k = 1; k <= h; k++) {
            for(int i = 1; i <= n; i++) {
                int temp = table[k - 1][i];
                table[k][i] = table[k - 1][temp];
            }
        }
    }

 

 

이제 1,2,4,8... 번째 이동한 결과를 모두 저장했으니 쿼리를 계산할 메소드하나만 선언해 주도록 하겠다.

 

임의의 노드 val에서 k번 이동한 값을 찾는 메소드이다.

 

현재 희소배열의 행은 순차적으로 1,2,3..으로 저장되어 있으니 값을 찾을땐 2^i 의 보정 작업을 통해

값을 찾아주면 된다.

 

    public int getVal(int val, int k) {
        for(int i = h; 0 <= i; i--) {
            if(k >= (1 << i)) {
                val = table[i][val];
                k -= (1 << i);
            }
        }
        return val;
    }

 

 

이제 한번 예시로 들었던 그래프의 데이터를 넣어 확인 해보도록 하겠다.

 

        List<Integer> parents = new ArrayList<>();
        parents.add(null);
        parents.add(3);
        parents.add(1);
        parents.add(4);
        parents.add(8);
        parents.add(2);
        parents.add(5);
        parents.add(4);
        parents.add(2);
        parents.add(5);
        parents.add(6);

        SparseTable sparseTable = new SparseTable(parents, 10, 100);

        sparseTable.setTable();
        System.out.println(sparseTable.getVal(1, 5));

 

 

앞서 표를 통해 얻은 값을 동일하게 출력하는것을 확인 할수 있다.

 

아래는 코드의 전문이다.

 

package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 스파스 테이블 알고리즘 : 최소 공통 조상 선행 알고리즘
 */
public class SparseTable {

    private final List<Integer> parents;
    private int[][] table;
    private int n, h;

    public SparseTable(final List<Integer> parents, int n, int h) {
        this.parents = parents;
        this.n = n;
        this.h = getLog(h);
        table = new int[this.h + 1][n + 1];
    }

    private int getLog(int maxHeight) {
        return (int) Math.ceil(Math.log(maxHeight) / Math.log(2)) + 1;
    }

    public void setTable() { // 1부터 시작한다고 가정.
        for(int i = 1; i <= n; i++) {
            table[0][i] = parents.get(i);
        }
        for(int k = 1; k <= h; k++) {
            for(int i = 1; i <= n; i++) {
                int temp = table[k - 1][i];
                table[k][i] = table[k - 1][temp];
            }
        }
    }

    public int getVal(int val, int k) {
        for(int i = h; 0 <= i; i--) {
            if(k >= (1 << i)) {
                val = table[i][val];
                k -= (1 << i);
            }
        }
        return val;
    }

    public static void main(String[] args) {
        List<Integer> parents = new ArrayList<>();
        parents.add(null);
        parents.add(3);
        parents.add(1);
        parents.add(4);
        parents.add(8);
        parents.add(2);
        parents.add(5);
        parents.add(4);
        parents.add(2);
        parents.add(5);
        parents.add(6);

        SparseTable sparseTable = new SparseTable(parents, 10, 100);

        sparseTable.setTable();
        System.out.println(sparseTable.getVal(1, 5));
    }


}

 

여담

 

최소 공통조상 알고리즘을 포스팅 하기 전에 알고가면 좋을 알고리즘을 먼저 정리해보았다.

아마 스파스 테이블을 숙지하고 최소 공통 조상 (LCA)로 넘어간다면 쉽게 이해할 수 있을듯 하다.