Algorithm] Segment Tree(구간 트리) - 1

 

 

 

알고리즘 문제를 풀면서 접했던 문제 중 하나로 순서가 정해지지 않은(정렬되지 않은) 방대한 데이터를 입력 받아 특정 구간에서의 최솟값을 구하는 문제가 있었다.

 

하나씩 모두 비교하는 방법을 사용하는 건 구현은 간단하지만, 전체 구간에 대한 최솟값을 구하는 경우 O(N)의 시간 복잡도를 갖게 되고, 거기에 이러한 쿼리가 최대 M회 실시된다고 하면 O(NM)이며, 쿼리가 N에 근접하는 문제의 경우 O(N^2)의 시간 복잡도로 실행 시간 초과가 발생할 수 있다.

 

구간별 최솟값을 구해두고 쿼리에 대응하는 방법을 고안해도, 최초 구성 단계에서의 시간 복잡도의 문제가 있고, 내용을 바꾸는 쿼리가 존재한다면 재구성하는 과정에서 시간 투자가 필요하기 때문에, 아무래도 기존의 단순 비교 방식을 이용한 구간 내 최솟값 산출은 무리가 있다.

 

이런 경우에 이용하기 좋은 구조가 하나 있는데, 바로 Segment Tree(구간 트리)다.

 

 

 

 

눈치가 빠른 사람들은 리프 노드는 값 그 자체를 의미하고, 내부 노드가 자식 노드 중에서 작은 값을 대표한다는 것을 알아챘을 것이다.

 

트리의 리프, 내부노드의 값은 구간에서의 값(여기서는 최솟값)을 대표한다. 리프 노드는 데이터 그 자체이면서, 구간 크기가 1인 경우의 값을 나타내고, 내부노드의 경우 자식노드들을 포함하는 구간에서의 값을 나타낸다.

 

이렇게 트리로 구조를 구성하면, 트리를 탐색하는 것만으로도 구간 내에서의 원하는 값을 얻어낼 수 있어 최솟값 탐색에 필요했던 시간을 O(N)에서 O(logN)으로 줄일 수 있다.