[JAVA] 백준 #10868 최솟값 | 세그먼트 트리 | 시간 초과 해결 방법 | 구간 최솟값 구하기

[JAVA] 백준 #10868 최솟값

10868번: 최솟값

🔒 문제

N(1 ≤ N ≤ 100,000) 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000) 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1 이상 1,000,000,000 이하의 값을 갖는다.

⌨️ 입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

🖥️ 출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.

---

 

🔹 1차 풀이: 선형 구조 사용 -> 시간 초과

 

	public static int getMin( int from, int to ){
        int min = 1000000001;

        for( int i = from; i <= to; i++ ){
            if( min > numbers[i] ) min = numbers[i];
        }

        return min;
    }

우선 1차 풀이는 가장 단순하게 선형 구조 배열에서 인덱스로 범위를 찾아 최솟값을 반환하도록 구현했다. 위 코드는 그중 최솟값을 찾는 메서드이다. 골드 문제가 이렇게 쉽게 풀릴 리가 없지 역시 시간 초과 오답이었다. 

이번 문제를 통해 '세그먼트 트리' 자료구조에 대해 자세히 학습하고 그 효율성을 체감할 수 있었다. 그 내용을 공유하고자 한다.

Segment Tree ( 세그먼트 트리 )

세그먼트 트리(Segment Tree)는 연속적인 여러 개의 데이터가 존재할 때, 특정 범위 데이터만 처리하기 위해 사용하는 자료구조이다. 

데이터의 수가 N일 때, 배열에서 인덱스를 사용해 최솟값을 구할 때와 세그먼트 트리를 사용할 때의 시간 복잡도 차이를 확인해 보면 다음과 같다. 

 

	선형 구조	세그먼트 트리 구조
데이터를 변경하는 과정	O(1)	O(logN)
최솟값을 구하는 과정	O(N)	O(logN)
최솟값을 구하는 행위를 M번 진행	O(NM)	O(MlogN)

 

이렇게 데이터 개수가 많아질수록 선형 구조와 세그먼트 트리 구조의 효율성 차이는 더욱 커진다. 

그럼 세그먼트 트리를 구현해 보자!

 

우선 명칭은 세그먼트 트리지만 배열로 간단하게 구현할 수 있다. 각 노드는 다음과 같은 규칙을 가지고 있다.

왼쪽 자식 노드의 인덱스 = 부모 노드 인덱스 * 2
오른쪽 자식 노드의 인덱스 = 부모 노드 인덱스 * 2 + 1

 

이렇게 부모 인덱스에 2를 곱하면 자식 노드에 접근할 수 있는 것이다.

또한 각 자식 노드는 부모의 범위( start, end )에 반을 나눠서 전자( start, mid ), 후자( mid + 1, end )를 범위를 가지고 있다. 

현재 이 문제에서는 부모 노드에 들어가는 값은 두 자식 노드에 각각 들어있는 최솟값 둘 중 더 작은 값을 담는다. 

 

 

1. 세그먼트 트리 크기( 노드 개수 ) 구하기 

위 규칙을 가지고 Tree 배열을 구현하기 전에 먼저 배열을 선언하려면 배열 크기를 알아야 한다. 세그먼트 트리 배열 크기는 어떻게 알 수 있을까? 

사실 세그먼트 트리를 구현할 배열의 크기는 [넉넉히 크면 된다]

무슨 말이냐 하면 내가 필요한 크기 딱 그 이상만큼만 있으면 메모리는 더 차지하지만 편리하게 이용할 수 있다. 배열 다룰 때 흔히 arr.length를 사용해서 for문을 순회할 일이 없기 때문에 Index Out Of Range가 나지 않을 만큼 내가 사용할 최대 인덱스값을 모두 수용할 만큼의 넉넉한 크기의 배열을 선언하면 된다. 그러므로 정석적으로 트리 크기를 구해도 되고, 아니면 넉넉잡아서 구하는 방법도 있다. 

 

먼저 정석적으로 세그먼트 트리 사이즈를 구하는 방법은 다음과 같다. 

 

    // 세그먼트 트리 사이즈 구하기
    static int getTreeSize(){
        int h = (int)Math.ceil(Math.log(N)/Math.log(2);
        return (int)Math.pow(2,h+1);
    }

 

트리 사이즈 즉 노드의 총개수를 알려면 트리의 높이부터 구해야 한다.

세그먼트 트리는 부모의 범위를 자식이 각각 반으로 나누고 또 그 자식이 반으로 나누니까 이진트리임을 이해할 수 있다. 

이때, 리프 노드의 개수가 N일 때 이진트리의 높이는 log2(N)이다. 이때 2는 밑, N은 진수이다. 

 

이걸 코드로 표현하면 자바의 Math  패키지에서 log를 제공하는데 밑이 2인 경우는 제공하지 않으므로 Math.log(N)/Math.log(2) 이렇게 사용하면 2는 밑, N은 진수로 나타낼 수 있다. 그럼 일단 이렇게 해서 트리의 높이를 찾았다. 

그럼 배열의 크기는  2^(h+1)−1인데, 우린 배열의 가장 첫 인덱스가 0이 아닌 1부터 시작하므로 1을 다시 더해 그냥  2^(h+1)만 해주면 된다.

 

위 과정이 귀찮으면 그냥 N에 4를 곱하면 된다. 하지만 메모리 낭비가 발생할 수 있으니 지양하는 것이 좋다.

 

 

2. 세그먼트 트리 초기화 함수 init 구현

우선 numbers [] 배열은 입력받은 숫자가 순서대로 저장되어 있는 배열이고, 우리가 세그먼트 트리로 사용할 배열은 tree 배열이다. 

초기화할 때는 가장 맨 위 노드인 루트 노드부터 시작한다: init( 1, N, 1 )

 

    // 세그먼트 트리 초기화
    static int init( int start, int end, int node ){
        if( start == end ) return tree[node] = numbers[start];

        int mid = ( start + end ) / 2;

        return tree[node] = Math.min( init(start, mid, node * 2), init( mid+1, end, node * 2 + 1));

    }

 

예제를 예로 들어보면 init( 1, 10, 1)을 호출했을 때, 자식 노드로 init( 1, 5, 2), init( 6, 10, 3)이 호출된다. 

그렇게 쭉쭉 내려가다 보면 init( 1, 1, 16), init( 2, 2, 17)과 같이 'start = end'인 리프 노드가 나오는데 그땐 numbers에 저장되어 있는 숫자를 값으로 담아준다. 리프노드를 찾으면 재귀적으로 최솟값을 구해서 올라가고, 그럼 결국 마지막에 다시 1번 노드에 도착했을  때는 전체 배열의 최솟값인 5가 담아진다. 

 

이렇게 init을 실행한 결과는 다음과 같다. 

빨간색 숫자는 tree 배열의 인덱스, 노드 안에 [괄호]는 범위, 그리고 노드 안에 숫자는 노드에 저장된 값 즉 각 범위의 최솟값이다. 리프 노드는 노란색으로 하이라이트 해뒀다. 

사실 init을 이해하는 게 초반에 쉽지 않은데 직접 손코딩을 해서 인덱스를 하나하나 써보면서 이해해 보면 어렵지 않게 익힐 수 있다.

 

 

3. 구간 최솟값 구하기

그럼 이제 본격적으로 구간 최솟값을 구하는 코드를 보자. 

 

    // [ left ~ to ] 구간 최솟값 구하기
    static int getMin(int start, int end, int node, int from, int to ){
        // 범위 밖에 있는 경우
        if( from > end || to < start ) return Integer.MAX_VALUE;

        // 범위 안에 있는 경우
        if( from <= start && to >= end ) return tree[node];

        // 두 경우에 해당하지 않는다면 두 부분으로 나눠서 최솟값 구하기
        int mid = ( start + end ) / 2;
        return Math.min( getMin( start, mid, node * 2, from, to ), getMin( mid + 1, end, node * 2 + 1, from , to) );
    }

 

매개변수가 5개나 되는데 각각을 설명해 보자면 다음과 같다. 

start: 현재 노드의 범위의 시작점
end: 현재 노드의 범위의 시작점
node: 노드의 인덱스
from: 구하려는 구간 범위의 시작점
to: 구하려는 구간 범위의 시작점

 

먼저 구간 최솟값을 구할 때 경우를 크게 세 가지로 나눌 수 있다.

1. 현재 노드의 범위가 구간 범위와 겹치는 부분이 전혀 없는 경우: 구간에 해당하지 않으므로 max를 리턴한다.

2. 현재 노드의 범위가 구간 범위와 일치하거나 속하는 경우: 노드에 담긴 값을 리턴한다.

3. 현재 노드의 범위와 구간의 범위가 겹치긴 하는데 범위를 벗어나는 구간도 함께 있는 경우: 자식 노드에 대해 getMin을 호출해 범위에 들어갈 때까지 쪼개기 

 

주어진 예제에 대해 getMin 함수를 실행해 보면 먼저 구간이 3, 5일 경우 getMin 함수 실행 시 실질적으로 노드값을 리턴하는 노드는 아래 그림에 주황색으로 표시한 Tree [5], Tree [9]이다. 그리고 그 둘 중의 최솟값은 노드 5에 들어있는 38이므로 구간[3,5]의 최솟값은 38이다.

MIN(3,5)

 

같은 방법으로 구간이 6, 9일 경우 getMin 함수 실행 시 실질적으로 노드값을 리턴하는 노드는 아래 그림에 주황색으로 표시한 Tree [6], Tree [14]이다. 그리고 그 둘 중의 최솟값은 노드 3에 들어있는 20이므로 구간[6,9]의 최솟값은 20이다.

MIN(6,9)

 

마지막으로 구간이 8, 10일 경우 getMin 함수 실행 시 실질적으로 노드값을 리턴하는 노드는 아래 그림에 주황색으로 표시한 Tree [7], Tree [13]이다. 그리고 그 둘 중의 최솟값은 노드 7에 들어있는 5이므로 구간[8,10]의 최솟값은 5이다.

MIN(8,10)

 

 

🔹 세그먼트 트리 전체 코드

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int[] numbers;
    static int[] tree;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        numbers = new int[ N + 1 ];
        tree = new int[getTreeSize()];

        for( int i = 0; i < N; i++ ){
            numbers[i+1] = Integer.parseInt(bf.readLine());
        }
        
        init( 1, N, 1);
        
        for( int i = 0; i < M; i++ ){
            st = new StringTokenizer(bf.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            System.out.println( getMin(1, N, 1, from, to ) );
        }

    }

    // 세그먼트 트리 사이즈 구하기
    static int getTreeSize(){
        int h = (int)Math.ceil(Math.log(N)/Math.log(2);
        return (int)Math.pow(2,h+1);
    }

    // 세그먼트 트리 초기화
    static int init( int start, int end, int node ){
        if( start == end ) return tree[node] = numbers[start];

        int mid = ( start + end ) / 2;

        return tree[node] = Math.min( init(start, mid, node * 2), init( mid+1, end, node * 2 + 1));

    }

    // [ left ~ to ] 구간 최솟값 구하기
    static int getMin(int start, int end, int node, int from, int to ){
        // 범위 밖에 있는 경우
        if( from > end || to < start ) return Integer.MAX_VALUE;

        // 범위 안에 있는 경우
        if( from <= start && to >= end ) return tree[node];

        // 두 경우에 해당하지 않는다면 두 부분으로 나눠서 최솟값 구하기
        int mid = ( start + end ) / 2;
        return Math.min( getMin( start, mid, node * 2, from, to ), getMin( mid + 1, end, node * 2 + 1, from , to) );
    }
    
}