[PS를 위한 자료구조 9강] 머지 소트 트리의 개념과 구현

PS를 위한 자료구조 1-9강

# 머지 소트 트리 # 에 대해 알아보겠습니다.

​

다음의 문제를 봅시다.

​

[수열과 쿼리1]

https://www.acmicpc.net/problem/13537

​

​

이 문제를 해결하기 위해 다음과 같은 자료구조를 생각하면 어떨까요?

​

우리가 흔히 합병 정렬(merge sort)를 하는 과정은 다음과 같습니다.

​

1 2 3 4 5 6 7 8
   |       |
1 4 6 8|2 3 5 7
 |   |   |   |
1 8|4 6|2 7|3 5
| | | | | | | |
1 8 6 4 7 2 3 5
// 아래에서 위 순서로 진행

그런데 이 모습.. 어쩐지 눈에 익지 않나요?

그렇죠. 우리가 지금까지 공부한게 뭡니까. 세그먼트 트리입니다.

​

루트에서부터 분할해 나가고, 리프 노드부터 두 노드를 결합 및 정렬하면서 올라오는 구조처럼 보이죠..!

이것이 바로 머지 소트 트리입니다. 세그먼트 트리의 일종이라고도 볼 수 있겠네요.

​

그럼 이 머지 소트 트리를 가지고 위 문제를 어떻게 해결할 수 있을까요??

​

세그먼트 트리 문제를 해결할 때 처럼, 구간에 완전히 속하는 가장 큰 노드를 찾고,

k보다 큰 수의 개수를 모두 구해서 더해주면 되겠죠..!

​

그럼 머지 소트 트리를 설계해봅시다.

​

각 노드가 가지고 있어야하는 데이터는 바로 배열​입니다.

다만 배열의 크기가 유동적이므로, 동적배열을 이용해주도록 합시다.

(파이썬은 리스트, 자바, c++은 벡터)

동적배열 트리[사이즈]

머지 소트 트리의 핵심인 병합 함수를 만들어주겠습니다.

세그먼트 트리에서 설명했던 일종의 결합​으로 볼 수 있습니다.

def 병합(LEFT : 동적배열, RIGHT : 동적배열) -> 동적배열:
    # LEFT, RIGHT를 정렬된 상태로 합쳐 새로운 동적배열을 반환하는 함수
    동적배열 반환배열
    while i <= LEFT범위, j <= RIGHT범위:
        LEFT[i], RIGHT[j] 중 작은 것을 반환배열에 삽입
        LEFT라면 i증가, RIGHT라면 j증가
    return 반환배열

 

위 병합 함수는 C++에서는 놀랍게도 내장함수로서 제공하고 있습니다.

C++을 이용하시는 분들은 이용할 수 있습니다.

def 전처리(구간의왼쪽 : int = 1, 구간의오른쪽 : int = N, 노드 : int = 1) -> None:
    if 구간의왼쪽 == 구간의오른쪽:
        # 리프노드 도달
        트리[노드].삽입(해당값)
        return
    중간 = 구간의왼쪽 + 구간의오른쪽 >> 1
    전처리(구간의왼쪽, 중간, 노드<<1)
    전처리(중간+1, 구간의오른쪽, 노드<<1|1)
    트리[노드] = 병합(트리[노드<<1], 트리[노드<<1|1]);

머지 소트 트리는 아쉽게도 업데이트 함수는 없습니다.

사실 존재하더라도 큰 의미가 없습니다.

위 전처리 함수는 병합 정렬의 과정과 완전히 일치하기 때문에, 시간복잡도가 O(NlogN)이지만

업데이트를 한다면 다시 정렬해야하는 원소가 많습니다.

1개부터 2개, 4개, 8개... 정렬해야하므로 시간복잡도는 O(N)입니다.

업데이트 연산은 사실상 사용할수가 없겠죠.

​

쿼리 연산을 설계합시다.

​

def 쿼리(K : int, L : int, R : int, 구간의왼쪽 : int = 1, 구간의오른쪽 : int = N, 노드 : int = 1) -> int:
    # [L R]의 K 초과의 원소 갯수 세기
    if 구간의오른쪽 < L or R < 구간의왼쪽:
        return 0
    if L <= 구간의왼쪽 and 구간의오른쪽 <= R:
        # 구간에 속하는 노드면 배열 안에서 K초과 개수를 확인
        return K초과개수(트리[노드])
    중간 = 구간의왼쪽 + 구간의오른쪽 >> 1
    return 쿼리(K, L, R, 구간의왼쪽, 중간, 노드<<1) + 쿼리(K, L, R, 중간+1, 구간의오른쪽, 노드<<1|1)

사실상 세그먼트 트리의 연산과 비슷하죠?

K초과개수 함수는 여러분들이 직접 구현해보시기 바랍니다.

이번에는 구현 대신 정답 코드를 첨부합니다.

​

[재귀 방식 c++]

http://boj.kr/587bb5393d514dcb834992cf5c00cd7f

​

[비재귀 방식 c++]

http://boj.kr/ba7087303d784048afa4ef7987cb3731

​

[재귀 방식 파이썬]

http://boj.kr/974b259e5f9c43f0b44186353169c643

​

피드백 및 오류 지적은 언제나 환영입니다.

​

[K번째 수]

7469번: K번째 수 (acmicpc.net)

​

[서로 다른 수와 쿼리 1]

14897번: 서로 다른 수와 쿼리 1 (acmicpc.net)

​

질문은 댓글로 해주셔도 되고, 제 유튜브 채널을 방문해서 하셔도 되고, 오픈채팅방으로 하셔도 됩니다.

​

[유튜브 : 승욱은] 승욱은 - YouTube

[ 1:1 오픈채팅방] 카카오톡 오픈채팅 (kakao.com)

​