Coding Test/Tree

[1991] 트리 순회

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 분석 트리 순회(전위 순회, 중위 순회, 후위 순회), DFS 1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 karla.tistory.com 풀이 import sy..

트리 순회(전위 순회, 중위 순회, 후위 순회), DFS, 재귀

1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문 # 중위순회 출력 : 4 2 5 1 6 3 7 def inorder(v): if v > 7: return else: inorder(v * 2) print(v, end=' ') inorder(v * 2 + 1) inorder(1) 3. 후위 순회 하위 트리 모두 방문 후 뿌리(root)를 방문 #후위순회 출력 : 4 5 2 6 7 3 1 def postorder(v):..

[2042번] 구간합 구하기 (세그먼트 트리, 리프노드, 값 변경)

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 1. 트리 초기화하기 ➔ setTree(idx) 트리 크기(treeSize) = 2^(K+1) ..

[11438번] 최소 공통 조상 구하기 (트리, 제곱수 LCA, LCA 시간초과)

11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 분석 최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과) 최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식 karla.tistory.com 풀이 """ 두 노드 쌍 M개 LCA 구하기 노드의 개수 N(2~100,000) N-1줄 트리상 연결된 두 노드 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 ..

최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과)

최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2ᵏ번째 위치의 부모 노드까지 저장해 둬야함 원리 1. 부모 노드 저장 리스트 만들기 부모 노드 리스트 정의 : P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드 번호 내 바로 위에 있는 부모 노드뿐만 아니라, 내 자리에서 2ᵏ 칸 위에 있는 부모가 누군지 저장해놔야함 부모 노드 리스트의 점화식 : P[K][N] = P[K-1][P[k-1][N]] 예시) K = 2 N=12 가정 P[2][12] = P[1][P[1][12]] P[2][12] : 12번 노드의 2²번째 부모 = 1 P[1][12] = 12번 노드의..

세그먼트 트리, 인덱스 트리, 구간합

1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 모든 값을 update 해야함 ➔ 느림 데이터의 업데이트가 빈번하게 일어나게 되면 합배열 성능 측면에서 안좋음 ➔ 속도유지를 위해 세그먼트 트리 사용 2. 원리 1) 트리 초기화 하기 ⓪ 샘플데이터 {5, 8, 4, 3, 7, 2, 1, 6} ① 리스트 길이 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듬 2ᵏ≥ N을 만족하는 𝑘의 최솟값을 구한 후 2ᵏ * 2 N=8이므로 2³ ≥ 8 ➔ 2³ * 2 = 16 ② 시작 노드 : 2ᵏ ➔ 2³ = 8 ③ 리프 노드에 원본 ..