반응형 트리3 백준 3584번 가장 가까운 공통 조상 - C++ 풀이 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 단순한 LCA(Lowest Common Ancestor) 구하기 문제이다. N = 10,000 밖에 되지 않기 때문에 희소 테이블을 사용하지 않는 O(N)의 LCA로도 충분하다. #include #include #include using namespace std; const int MAX = 10'001; int N; int depth[MAX], parent[MAX]; vector children[MAX]; void dfs(int curr) { for (auto child: children[curr]) { depth[child] = depth[curr] + 1; dfs(child); } } int NC.. 2023. 8. 21. 프로그래머스 표현 가능한 이진트리 - C++ 풀이 1. 주어진 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 때, 부모는 더미노드인데 자식은 실제노드인 경우 표현 불가능한 구조이다. 1. 주어진 십진수를 이진수로 변환한다. 먼저 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 노드를 왼쪽부터 순서대로 살펴보는 것은 중위순회하는 것과 같다. 따라서 변환한 이진수는 트리를 중위순회한 결과와 같고, 이진수의 길이는 트리의 노드 개수와 같다. 포화이진트리는 노드의 개수가 2^n-1개이므로 포화이진트리가 되도록 부족한 길이는 0으로 채워준다. (더미 노드를 추가하는 것은 문제가 되지 않음) 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 .. 2023. 7. 22. 백준 4256번 트리 - C++ 풀이 1. root 노드는 preorder[0]이다. 2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다. 1. root 노드는 preorder[0]이다. 전위 순회 시 가장 먼저 방문하는 노드는 루트 노드이다. 2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다. 중위 순회 시 왼쪽 부트리 - 루트 - 오른쪽 부트리 순으로 방문한다. 전위 순회 결과에서 찾은 루트를 중위 순회 결과에서 찾는다. 그리고 루트보다 더 먼저 등장한 노드들로 왼쪽 부트리를 만들고, 루트보다 더 나중에 등장한 노드들로 오른쪽 부트리를 만드는 작업을 재귀적으로 반복해주면 원래 트리를 .. 2022. 7. 11. 이전 1 다음 반응형
