직장인의 개발 일기

1. 머지 소트 트리(Merge Sort Tree)

머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다.

2. 머지 소트 트리(Merge Sort Tree) 동작 원리

머지 소트 트리(Merge Sort Tree)는 각 노드에서 해당 노드에 포함된 모든 원소들을 정렬한 상태로 저장하는 트리입니다.

머지 소트 트리(Merge Sort Tree)는 아래와 같이 구성되어 있습니다.

3. 머지 소트 트리(Merge Sort Tree) 구현

1. 트라이(Trie)

트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다.

2. 트라이(Trie) 동작 원리

먼저 그림을 통해 살펴보도록 하겠습니다.

다음 그림은 문자열 {"jade", "japp", "an", "answer"}를 트라이(Trie)로 구현한 것입니다.

3. 트라이(Trie) 구현

트라이의 노드는 자손 노드를 가리키는 포인터 배열과, 문자열의 끝인지를 나타내는 bool 변수로 구성되어 있습니다.

보통 영어 소문자로만 이루어딘 경우가 대부분이기 때문에 배열의 크기를 26으로 선언합니다.

동적으로 메모리를 할당하기 때문에 delete로 해제해주는 것이 매우 중요합니다.

이제 문자열을 트라이에 넣어주는 함수에 대해 알아보겠습니다.

이미 트라이에 해당 문자에 해당하는 노드가 있다면 따라가고, 그렇지 않다면 새로 만들어줍니다.

문자열의 끝에 도달하면 end의 값을 true로 바꾸어줍니다.

마지막으로 트라이에서 찾고자 하는 문자열이 있는지 탐색하는 함수에 대해 알아보겠습니다.

만약 다음 문자로 가는 노드가 존재하지 않는다면 존재하지 않는 단어입니다.

또한, 문자열의 끝에 도달했을 때 end의 값이 true가 아니라면 존재하지 않는 단어입니다.

[ 소스코드 ]

1. 희소 배열(Sparse Table)

- 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열

- 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열

2. 희소 배열 만들기

보통 5번 노드에서 1번 노드까지 가기 위해서는 총 3번(5→3→6→1)의 이동이 필요합니다. 하지만 희소 배열로 이동을 한다면 총 2번의 이동이면 충분합니다. (3 = 2 + 1)

이처럼 간선을 1개씩 이동하지 않고, 1, 2, 4, 8... 과 같이 2^i씩 이동한다면 logn번 만에 원하는 노드에 도달할 수 있습니다.

[ 소스 코드 ]

1. 세그먼트 트리 (Segment Tree)

먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1,2,3,4,5} 일 때, 다음과 같은 그래프로 나타낼 수 있습니다.

각각의 노드들의 값은 자식 노드들의 값들을 더한 것입니다. 구간의 합을 구할 때 보통 O(N)의 시간이 걸리지만 세그먼트 트리를 이용한다면 O(logN)의 시간만에 값을 구할 수 있습니다.

트리를 만들기 위해서는 트리의 높이를 알아야 합니다. 트리의 높이를 알기 위해서는 리프노드의 수를 이용해야 하고, 다음과 같이 구할 수 있습니다.

트리의 높이 = ceil(log(N))

ceil은 어떤 수든 올림을 해서 구해주는 함수입니다. 따라서 log5 = 2.xxx이지만 ceil함수 안에 넣는다면 3이라는 수가 나오게 됩니다. 위의 그래프를 보면 루트 노드의 높이를 0이라고 했을 때 트리의 높이가 3인 것을 알 수 있습니다. 따라서 세그먼트 트리의 크기는 2^(트리의 높이 + 1)이 됩니다.

2. 세그먼트 트리 만들기

먼저 주어진 범위를 반으로 나누고, 나누어진 2개의 범위에 대해서 왼쪽과 오른쪽 범위에 대해 각각 재귀호출을 해줍니다. 이를 계속 반복해주다가 리프 노드에 다다르면 재귀를 멈춰주시면 됩니다.

이진트리이므로 항상 범위를 반으로 나누면 됩니다. 즉 (현재 노드, 시작 범위, 끝 범위)의 형태로 반복해서 재귀 호출을 해주고 마지막에 시작 범위와 끝 범위가 일치할 때가 리프 노드이므로 값을 넣어주고 그 값을 return 해주면 됩니다.

3. 세그먼트 트리 구간합 구하기

구간합을 구할 때 조건을 나누어 주면 쉽게 구할 수 있습니다. 

1. 현재 탐색하는 범위가 찾고자하는 범위와 완전히 겹치는 경우

2. 현재 탐색하는 범위가 찾고자하는 범위와 일부 겹치는 경우

3. 현재 탐색하는 범위가 찾고자하는 범위와 완전히 겹치지 않는 경우

이를 코드로 표현하면 다음과 같습니다.

4. 세그먼트 트리 값 바꾸기

특정 index의 값을 바꿀 때도 분기를 나누어서 구해주면 됩니다. 바꾸고자 하는 index가 현재 범위에 포함되어 있는지 없는지만 체크해주면 쉽게 구현할 수 있습니다.