Review 5 - 트라이/세그먼트 트리/최소 공통 조상

4. 트라이

1) In 연산

• In 연산의 시간 복잡도는 List나 Tuple에서 O(N), Set이나 Dictionary에서 O(1)이다.
• Set 자료구조에서는 add와 remove 메서드를 통해 원소를 삽입 및 삭제할 수 있다.

2) 트라이

① Node 클래스

class Node:

    def __init__(self, value):
        self.value = value
        self.children = {}
        self.isEnd = False # 단어의 끝 표시

② Trie 클래스

class Trie:

    def __init__(self):
        self.root = Node('') # 공백

    def insert(self, str): 
        node = self.root # 루트에서 시작
        
        for char in str:  # 삽입할 문자열의 각 문자
            if char not in node.children:  # root 노드의 children에 첫 문자가 없으면
                newNode = Node(char)  # 첫 문자를 갖는 새로운 노드 생성
                node.children[char] = newNode  # 생성된 노드를 root 노드의 자식 노드로 추가
                node = newNode  # 자식 노드로 이동
                
            else:
                node = node.children[char]
                
        node.isEnd = True  # 단어의 끝 표시

    def search(self, str):
        node = self.root # 루트에서 시작

        for char in str: # 탐색하려는 문자열의 각 문자
            if char in node.children: # root 노드의 children에 첫 문자가 있는 경우
                node = node.children[char] # 자식 노드로 이동

            else:  # root 노드의 children에 첫 문자가 없는 경우
                return False
            
        return node.isEnd # 문자열의 끝에 도달했을 때, 단어도 끝나는지 확인

③ 트라이의 단서

• 특정 접두사로 시작하는 모든 단어를 찾아야 하는 문제
• 문자열을 자동 완성해야 하는 문제

④ 입력 값의 개수를 알 수 없는 경우

• try-except 구문을 사용하여 처리한다.

while True:

    try: 
        N = int(input())
    except: 
        break

5. 세그먼트 트리

1) 특징

• Full Binary Tree이므로, 배열을 이용한 트리 표현을 사용한다. (1번 인덱스를 루트로 간주)
• 데이터의 업데이트가 잦은 환경에서의 구간 합, 최대/최소 값을 구하기에 유리하다.

2) 세그먼트 트리 생성하기

• 데이터가 N개 존재할 때, 배열의 Size는 2 ^ k ≥ N을 만족하는 k의 최소 값에 대해 2 ^ k * 2를 계산한 수치가 된다.
• 모든 데이터는 리프 노드에 할당되어야 하므로, 리프 노드의 시작 인덱스인 2 ^ k부터 차례대로 데이터를 삽입한다.
• i 노드의 왼쪽 자식은 2i, 오른쪽 자식은 2i + 1인 것을 이용하여 구간 합, 최대 값, 최소 값 중 알아내고자 하는 값을 계산한다.

length = N
height = 0 # k 값

while length > 0: # 2 ^ k ≥ N을 만족하는 k의 최소 값을 구하는 과정
    length //= 2
    height += 1

treeSize = 2 ** (height + 1) # 트리 배열의 사이즈(= 2 ^ k * 2)
leafStartIdx = 2 ** height # 리프 노드의 시작 인덱스
tree = [0] * (treeSize) 

# 데이터를 리프 노드에 저장
for i in range(leafStartIdx, leafStartIdx + N): # 기존 배열의 원소 수가 리프 노드 수보다 작거나 같으므로, treeSize를 끝 범위로 설정하면 안됨.
    tree[i] = int(input())

# 나머지 노드에 값 할당
def setTree(i):
    while i > 1: # 루트 노드까지만 구하면 됨.
        tree[i // 2] += tree[i] # 자식 노드의 인덱스가 2i, 2i + 1인 것을 이용하여 구간 합 계산 
        i -= 1
        
setTree(treeSize - 1) # 높은 인덱스에서 낮은 인덱스 순서로 노드에 값을 할당

3) 데이터 업데이트

① 구간 합

• 모든 부모(조상) 노드의 값에, 새로운 데이터와 기존 데이터 사이의 차이만큼을 더한다.

② 최대/최소 값

• 변경된 노드를 기점으로 최대/최소를 다시 계산한다.
• 최대/최소 값이 갱신되지 않았다면, 업데이트를 종료한다.

# 데이터 업데이트 함수
def updateValue(index, value):
    diff = value - tree[index] # 기존 데이터와 새로운 데이터 간의 차이
    
    while index > 0: # 루트 노드에 이르기까지 모든 부모(조상) 노드의 값에 diff만큼을 더함
        tree[index] = tree[index] + diff
        index //= 2

4) Range Query 값 구하기

① Query Range를 트리 배열에 알맞게 변경한다.

• 원래의 범위에서 2 ^ k - 1만큼 평행 이동하여, 세그먼트 트리의 range로 변경할 수 있다.

② Query 값 구하기

• 구간 합, 최대/최소 값을 구하는 데에 필요한 노드를 선택한다.
• start 인덱스의 값이 홀수이거나, end 인덱스의 값이 짝수인 경우 해당 노드를 선택하고, 옆 노드(start 기준 오른쪽, end 기준 왼쪽 노드)의 부모 노드로 이동한다.
• 반대로 start 인덱스의 값이 짝수이거나, end 인덱스의 값이 홀수인 경우 부모 노드로 이동한다.
• 위 과정을 start > end가 될 때까지 반복한다.

# 구간 합 계산 함수
def getIntervalSum(start, end):
    intervalSum = 0

    while start <= end:
        if start % 2 == 1: # start의 인덱스가 홀수이면, 해당 노드의 값을 intervalSum에 포함
            intervalSum += tree[start]

        if end % 2 == 0: # end의 인덱스가 짝수이면, 해당 노드의 값을 intervalSum에 포함
            intervalSum += tree[end]

        # 부모 노드로 이동
        start = (start + 1) // 2
        end = (end - 1) // 2

    return intervalSum
    
for i in range(M):
    query, start, end = map(int, input().split())

    if query == 1: # start번째 값을 end로 업데이트
        updateValue(start + leafStartIdx -1, end) # 기존 배열의 range를 세그먼트 트리의 range로 변경하하기 위해 2 ^ k - 1만큼 평행 이동
    
    elif query == 2: # start부터 end까지의 구간 합 
        start = start + leafStartIdx -1
        end= end + leafStartIdx -1
        print(getIntervalSum(start, end))

5) 주의 사항

① 배열 초기화

• 구간 합:트리 배열의 모든 원소를 0으로 초기화한다.
• 최대/최소 값
  • 최대 값을 구하는 경우: 트리 배열의 모든 원소를 0으로 초기화한다.
  • 최소 값을 구하는 경우: 트리 배열의 모든 원소를 sys.maxsize로 초기화한다.
• 구간 곱: 트리 배열의 모든 원소를 1로 초기화한다.

② 구간 곱의 데이터 업데이트

• 구간 합 세그먼트 트리와 달리 구간 곱 세그먼트 트리를 업데이트 할 때에는, 변경된 자식의 옆 자식까지 고려하여 부모 노드의 값을 다시 계산해야 한다.

def updateValue(index, value):
    tree[index] = value
    index //= 2

    while index > 0:
        tree[index] = (tree[index * 2] * tree[index * 2 + 1]) 
        index //= 2

6. 최소 공통 조상

1) 아이디어

① 일반 LCA

• DFS를 통해 각 노드의 부모 노드와 깊이를 배열에 저장한다. (1번 인덱스를 루트로 간주)
• 선택된 두 노드의 깊이가 다를 경우, 깊이가 같아질 때까지 부모 노드로 이동한다. (이 과정에서 두 노드가 같아질 경우, 해당 노드가 최소 공통 조상이 된다.)
• 깊이가 같아지면, 두 노드 모두 부모 노드로 이동한다. 이 때, 처음으로 만나게 되는 노드가 최소 공통 조상이 된다.

② 개선된 LCA

• P[K][N] = P[K-1][P[K-1][N]] 점화식을 이용하여, 각 노드의 2 ^ K(= 0, 1, 2, ...)번째 부모 노드를 배열에 저장한다.
• 여기서 K 값은, 트리의 깊이 > 2 ^ K를 만족하는 최대 값으로 결정된다.
• K 값과 점화식을 이용해 부모 노드 배열을 완성한다.
• depth 배열에 노드의 깊이를 저장한 후, 선택된 두 노드의 깊이 차이(D)를 구한다.
• 2 ^ K < D를 만족하는 K의 최대 값을 이용해, 깊이가 같아질 때까지 2 ^ K번 째 부모 노드로 이동한다.
• 깊이가 맞추어졌다면, K를 최대값에서 1씩 감소시켜 가면서, 최초로 두 부모 노드가 달라지는 K 값을 찾는다. K 값을 찾았다면, K 번째 부모 노드로 이동한다.
• 계속해서 K 값을 감소시키다가 K가 0이 되면 반복문을 종료한다. 이 때, 두 노드가 동일한 노드이면 해당 노드가 최소 공통 조상이 되고, 다른 노드이면 두 노드의 부모 노드가 최소 공통 조상이 된다.

2) 알고리즘 선택

트리의 깊이는 최악의 경우 노드의 개수(N)와 같으므로, 일반 LCA의 최대 시간 복잡도는 O(N)이다. 질의의 개수가 M일 때 시간 복잡도는 O(NM)이 되므로, 이 값이 시간 제약을 초과할 경우에는 개선된 LCA를 사용해야 한다.