# LCA
.png)
<Baekjoon> #3584_LCA, DFS 가장 가까운 공통 조상 java
\[BOJ 참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..) 문제 제목에서도 주어진대로 가장 가까운
[백준]3176 도로 네트워크
N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오
Lowest Common Ancestor (LCA)
Tree에서 u, v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다. 그렇다면 어떻게 LCA를 구할 수 있을까? Method 1 Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다. root에서 u, v까지의 경로를
3176. 도로 네트워크
시간 제한: 1초메모리 제한: 256MB먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이
15480. LCA와 쿼리
시간 제한: 2초메모리 제한: 512MBroot가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능 하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 1을 root로
1761. 정점들의 거리
시간 제한: 2초메모리 제한: 128MB두 정점을 잇는 경로를 찾아내야 한다. 이때, 두 정점을 잇는 최상단 node인 Lowest common ancestor(LCA)를 찾으면 경로를 쉽게 이을 수 있을 것이다.1번 node를 root로 하여, DFS를 진행하여 다음
백준 11438 LCA2
https://www.acmicpc.net/problem/11438LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다. 두 노드의 최소공통조상을 찾는 방법은1\. 두 노드의 높이를 맞춘다.2\. 노드를 올려보면서 부모가 같은지
.JPG)
[백준 - 11438] LCA2
문제링크11437-LCA 풀이와 비슷하지만, 공통 부모를 찾는 과정에 차이점이 있습니다.node의 2^0, 2^1, ... 번째 parent를 저장합니다.항상 node2의 깊이가 더 깊다고 가정하고, 두 node의 깊이 차이를 통해 node2를 node1과 같은 깊이에
[백준 - 11437] LCA
문제링크dfs를 통해 각 node의 depth를 계산합니다.LCA를 구할 두 node의 depth를 동일하게 만듭니다.두 node의 parent가 같아질 때까지 두 node의 parent를 비교합니다.
[백준] 3584번 - 가장 가까운 공통 조상 Python, Java
루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가
알고리즘 - 최소 공통 조상(Lowest Common Ancestor)
최소 공통 조상(LCA) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제다.위의 그래프에서 8번 노드와 15번 노드의 LCA는 2번 노드다.3번 노드와 15번 노드의 LCA는 1번 노드다.모든 노드에 대한 깊이(depth)를 계산한다.최소 공통 조상
하루일지 - 10
매출 첫 6조 카카오…"3000억 자사주 소각" 주주 달래기카카오는 회사가 너무 커졌는데 나온는 얘기들도 너무 많은 것 같다.선점의 대표적 주자가 아닌가 싶다. 역시 돈 내고 쓰던거 무료로 쓰게 해주는 건우선적으로 할 경우 시장을 먹고 그렇게 뻗어 나가는 것이 가장 좋
백준 3584, 가장 가까운 공통 조상 - Tree, DFS, DP, LCA (Lowest Common Ancestor)
https://www.acmicpc.net/problem/3584루트 노드 찾기입력 트리 노드 정보가 "부모 노드 - 자식 노드" 형태로 주어짐트리 노드 정보 입력할 때, 자식 노드들을 방문 처리=> 입력이 끝난 후, 방문되지 않은 노드가 루트 노드1) 모든
BOJ 1626 두 번째로 작은 스패닝 트리
https://www.acmicpc.net/problem/1626시간 2초, 메모리 128MBinput :V E(1 ≤ V ≤ 50,000, 1 ≤ E ≤ 200,000)u v w(0 <= w < 100,000)output : 두 번째로 작은 스패닝
BOJ 15481 그래프와 MST
https://www.acmicpc.net/problem/15481시간 2초, 메모리 512MBinput :N M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000)u v w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10^9) out
[알고리즘] 최소공통조상(LCA)
1. 최소공통조상 LCA, Lowest common ancestor. 두 노드의 공통된 상위 부모노드(조상) 중에서, 가장 가까운 부모노드를 의미한다. 위 graph(tree)에서 8번노드와 15번노드의 LCA는 2번노드가 된다. 2. 해 도출 과정 모든 노드
LCA
입력의 크기가 매우 작아서 단순한 알고리즘으로도 풀린다.우선, 입력에 별도로 부모 자식 관계가 주어지지는 않으므로 입력을 그래프로 간주하여 받은 뒤 루트를 1번 노드로하는 BFS 트리를 생성해준다.이 때 각 노드의 깊이를 함께 구해주도록 하자.만약, a와 b의 LCA를