어흥

문제 링크: www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 주의할 점 - LCA 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 수행되는 알고리즘을 이해하도록 한다 2. 구현 - 모든 변에 대해 입력받은 후, havePar[] 배열을 통해 트리의 Root를 찾는다 - DFS() 함수를 통해 각 Node의 트리에서 높이를 구한다 - Make_tree() 함수를 통해 N번째 Node의 2^i번째 높..

문제 링크: www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem Binary Search Tree : Lowest Common Ancestor | HackerRank Given two nodes of a binary search tree, find the lowest common ancestor of these two nodes. www.hackerrank.com 1. 주의할 점 - LCA 정석풀이로 풀 수 있지만, BST의 특성을 활용하면 쉽게 풀 수 있다 - LCA, BST에 대해 알고 있어야 한다 2. 구현 - BST란? 1개의 Node에 최대 2개의 자식이 존재할 수 있다. 또한, 현재 Node를 기준으로 ..