2017. 2. 19. 13:01
SegmentTree(구간트리) 알고리즘-자료구조2017. 2. 19. 13:01
어떤 수의 배열이 주어지고, ex) 1, 4, 5, 3, 2 이 중에서 3번째부터 5번째 수까지의 중 최소값을 구하라는 문제가 있다면,
일반적인 방법으로는 주어진 구간을 순회하면서 최소값을 찾는 과정을 거쳐야 할 것이다.
한 두번정도라면 문제가 되지 않겠지만, 기본적으로 시간이 O(n)이 걸리기 때문에 질의가 여러번 들어온다면 시간이 많이 소요된다.
그에 반해 세그먼트 트리를 구현하면 각 질의에 대해서 O(log N)의 시간안에 답을 구할 수 있다.
구현 방법에 따라, 최소값 만이 아니라 최대값이나 구간의 합 등 다양한 응용이 가능하다.
https://gist.github.com/woo972/aa4934738624c7f0c1eb708c725a39d4
'알고리즘-자료구조' 카테고리의 다른 글
| 병합정렬(Merge Sort) (0) | 2017.04.29 |
|---|
