BaekJoon 17435번 : 합성함수와 쿼리 (python)

📝 BaekJoon 17435번 : 합성함수와 쿼리 (G1 52.213%)

---

🔎 합성함수와 쿼리 문제

---

📌 아이디어

효율적인 최소 공통 조상 LCA알고리즘을 구현하기 위해서 sparse Table자료구조를 사용할 수 있다.

---

💭 풀이

• sparse table은 모든 계산값을 저장하는 것이 아니라 지수배로 늘어나는 결과 값을 저장하여 비트 연산을 통해 기존의 O(n*n)의 시간복잡도를 O(nlogn)의 시간복잡도로 계산할 수 있게 해준다.
• sparse_table[node][cap]은 'node'노드에서 시작하여 2^cap 높이 만큼 올라갔을 때의 조상을 의미하게 된다. 이때 sparse_table[node][cap]을 채우기 위해 cap-1높이의 조상을 사용하고 다시 한 번 해당 조상의 cap-1을 찾아 [node][cap]을 채워준다.
  재귀함수로 sparse[node][cap] = sparse[sparse[node][cap-1]][cap-1]을 만족한다.
• 위의 과정을 통해sparse table[i][j]는 i번째 원소의 2^j의 원소값을 저장한다. 이를 통해 입력으로 주어지는 n,k에 대하여 n을 2진수 bit연산자로 보았을 때 1이 존재하는 자리마다 cur=sparse_table[cur][i]값으로 업데이트 해주게 된다.

---

💻 코드

import sys
input = sys.stdin.readline

m = int(input())
func = list(map(int,input().split()))
root = [0]*(m+1)
edge = [[] for _ in range(m+1)]
capacity = 20

for i in range(1, m+1) :
    root[i] = func[i-1]

sparse_table = [[0]*20 for _ in range(m+1)]

for node in range(1, m+1) :
    sparse_table[node][0] = root[node]

for cap in range(1, capacity) :
    for node in range(1, m+1) :
        par = sparse_table[node][cap-1]
        sparse_table[node][cap] = sparse_table[par][cap-1]

#print(sparse_table)

T = int(input())
for _ in range(T) :
    n, x = map(int,input().split())

    cur = x
    for i in range(capacity) :
        if n & (1<<i) :
            cur = sparse_table[cur][i]
    print(cur)

---