# LCA

41개의 포스트

LCA(최소공통조상)

find cntfind parents

2022년 7월 27일
·
0개의 댓글
·
post-thumbnail

<Baekjoon> #3584_LCA, DFS 가장 가까운 공통 조상 java

\[BOJ 참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..) 문제 제목에서도 주어진대로 가장 가까운

2022년 7월 17일
·
0개의 댓글
·
post-thumbnail

[백준]3176 도로 네트워크

N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오

2022년 4월 18일
·
0개의 댓글
·

Lowest Common Ancestor (LCA)

Tree에서 u, v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다. 그렇다면 어떻게 LCA를 구할 수 있을까? Method 1 Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다. root에서 u, v까지의 경로를

2022년 4월 15일
·
0개의 댓글
·

3176. 도로 네트워크

시간 제한: 1초메모리 제한: 256MB먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이

2022년 4월 13일
·
0개의 댓글
·

15480. LCA와 쿼리

시간 제한: 2초메모리 제한: 512MBroot가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능 하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 1을 root로

2022년 4월 12일
·
0개의 댓글
·

1761. 정점들의 거리

시간 제한: 2초메모리 제한: 128MB두 정점을 잇는 경로를 찾아내야 한다. 이때, 두 정점을 잇는 최상단 node인 Lowest common ancestor(LCA)를 찾으면 경로를 쉽게 이을 수 있을 것이다.1번 node를 root로 하여, DFS를 진행하여 다음

2022년 4월 11일
·
0개의 댓글
·

백준 11438 LCA2

https&#x3A;//www.acmicpc.net/problem/11438LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다. 두 노드의 최소공통조상을 찾는 방법은1\. 두 노드의 높이를 맞춘다.2\. 노드를 올려보면서 부모가 같은지

2022년 4월 6일
·
0개의 댓글
·
post-thumbnail

[백준 - 3584] 가장 가까운 공통 조상

문제링크LCA2 문제풀이를 참고해주세요.

2022년 3월 13일
·
0개의 댓글
·
post-thumbnail

[백준 - 11438] LCA2

문제링크11437-LCA 풀이와 비슷하지만, 공통 부모를 찾는 과정에 차이점이 있습니다.node의 2^0, 2^1, ... 번째 parent를 저장합니다.항상 node2의 깊이가 더 깊다고 가정하고, 두 node의 깊이 차이를 통해 node2를 node1과 같은 깊이에

2022년 3월 12일
·
0개의 댓글
·
post-thumbnail

[백준 - 11437] LCA

문제링크dfs를 통해 각 node의 depth를 계산합니다.LCA를 구할 두 node의 depth를 동일하게 만듭니다.두 node의 parent가 같아질 때까지 두 node의 parent를 비교합니다.

2022년 3월 11일
·
0개의 댓글
·

[백준] 3584번 - 가장 가까운 공통 조상 Python, Java

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가

2022년 3월 10일
·
0개의 댓글
·
post-thumbnail

알고리즘 - 최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(LCA) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제다.위의 그래프에서 8번 노드와 15번 노드의 LCA는 2번 노드다.3번 노드와 15번 노드의 LCA는 1번 노드다.모든 노드에 대한 깊이(depth)를 계산한다.최소 공통 조상

2022년 3월 10일
·
0개의 댓글
·

하루일지 - 10

매출 첫 6조 카카오…"3000억 자사주 소각" 주주 달래기카카오는 회사가 너무 커졌는데 나온는 얘기들도 너무 많은 것 같다.선점의 대표적 주자가 아닌가 싶다. 역시 돈 내고 쓰던거 무료로 쓰게 해주는 건우선적으로 할 경우 시장을 먹고 그렇게 뻗어 나가는 것이 가장 좋

2022년 2월 11일
·
0개의 댓글
·
post-thumbnail

백준 3584, 가장 가까운 공통 조상 - Tree, DFS, DP, LCA (Lowest Common Ancestor)

https&#x3A;//www.acmicpc.net/problem/3584루트 노드 찾기입력 트리 노드 정보가 "부모 노드 - 자식 노드" 형태로 주어짐트리 노드 정보 입력할 때, 자식 노드들을 방문 처리=> 입력이 끝난 후, 방문되지 않은 노드가 루트 노드1) 모든

2022년 2월 7일
·
0개의 댓글
·
post-thumbnail

BOJ 1626 두 번째로 작은 스패닝 트리

https&#x3A;//www.acmicpc.net/problem/1626시간 2초, 메모리 128MBinput :V E(1 ≤ V ≤ 50,000, 1 ≤ E ≤ 200,000)u v w(0 &lt;= w &lt; 100,000)output : 두 번째로 작은 스패닝

2022년 1월 28일
·
0개의 댓글
·
post-thumbnail

BOJ 15481 그래프와 MST

https&#x3A;//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

2022년 1월 28일
·
0개의 댓글
·

[알고리즘] 최소공통조상(LCA)

1. 최소공통조상 LCA, Lowest common ancestor. 두 노드의 공통된 상위 부모노드(조상) 중에서, 가장 가까운 부모노드를 의미한다. 위 graph(tree)에서 8번노드와 15번노드의 LCA는 2번노드가 된다. 2. 해 도출 과정 모든 노드

2022년 1월 27일
·
0개의 댓글
·
post-thumbnail

LCA

입력의 크기가 매우 작아서 단순한 알고리즘으로도 풀린다.우선, 입력에 별도로 부모 자식 관계가 주어지지는 않으므로 입력을 그래프로 간주하여 받은 뒤 루트를 1번 노드로하는 BFS 트리를 생성해준다.이 때 각 노드의 깊이를 함께 구해주도록 하자.만약, a와 b의 LCA를

2021년 12월 14일
·
0개의 댓글
·