[알고리즘 공부] 머지 소트 트리

0. 개요

예전에 도전했다가 못 풀었던 문제 중 시도해 볼만한 문제가 있는지 찾아봤다.

그 문제는 바로 백준의 K 번째 수였다.

주어진 배열에서 s번째에서 e번째 숫자까지 정렬하고, 그중 k 번째 수를 찾는 문제였다.

지금이었으면 세그먼트 트리를 사용해서... 아마... 풀지.. 않았을까..?

그래서 이번에는 세그먼트 트리를 이용한 자료구조 중 하나인 머지 소트 트리에 대해 공부해보았다.

 

1. 알고리즘 개념

머지 소트 트리는 세그먼트 트리의 각 노드에 해당 구간의 원소들을 정렬한 배열을 저장한 자료구조이다.

따라서 정렬된 구간을 이용한 문제들을 빠르게 처리할 수 있다.

이때는 보통 O(long^2 N)안에 처리된다.

 

2. 알고리즘 구조

 

기본적으로 세그먼트 트리 형태로 생겼으며,

각 노드는 노드의 속성에 따라 다른 값이 저장된다.

 

1) 리프 노드

배열의 하나의 값만 들어가 정렬된 상태

 

2) 부모 노드

양쪽 자식을 merge 한 상태

 

리프 노드에서 부모 노드로 올라가며, merge 하는 형태이기에 "머지" 소트 트리라고 부른다.

 

 

머지 소트 트리는 특정 연산을 처리할 때 O(long^2 N) 만큼 걸리는데, 이는

 

1. 특정 구간에 해당하는 노드를 세그먼트 트리 방식으로 찾기 (O(log N))

2. 각 노드에 저장된 정렬된 배열에서 특정 쿼리에 따라 값을 찾기 (O(long N))

 

만큼 걸리기 때문에 총 O(long^2 N)만큼 걸리게 된다.

 

 

배열을 한번 저장해두고 처리하는 자료구조이기 때문에

내용의 수정이 거의 일어나지 않고, 특정 구간 안에 정렬된 기반 질의를 반복적으로 해야하는 상황에 사용될 수 있다.