백준/트리
-
백준 5639 nodejs백준/트리 2023. 1. 3. 12:47
문제 https://www.acmicpc.net/problem/5639 풀이 전위 순회의 첫 노드가 루트, 후위 순회의 마지막 노드가 루트임을 이용해 재귀 또는 반복으로 답을 구한다. (2263번 참조) 재귀 let I = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number) let O = [] function F(s, e) { if (s >= e) return let mid = e for (let i = s; i I[s] && (mid = i)) break O.push(I[s]) F(mid, e) F(s + 1, mid) } F(0, I.length) console.log..
-
백준 2263 nodejs백준/트리 2022. 12. 28. 12:41
문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 후위 순회[c3, c4]의 마지막 노드가 루트임을 이용하여 중위 순회[c1, c2]에서 루트의 위치(i)를 찾는다. 루트의 위치를 이용해 중위 순회([c1, i - 1], [i + 1, c2])와 후위 순회([c3, c3 + i - c1 - 1], [c3 + i - c1, c4 - 1])를 왼쪽과 오른쪽 그룹으로 나눈다. 재귀 호출하거나 반복한다. 중위 순회의 index 정보 i를 미리 저장해서 탐색 시간을 줄일..