Dev_Diary

https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 우선 최소 공통 조상을 구한 뒤, 쿼리의 종류에 따라 출력해주면 되는 문제입니다. LCA 를 구한 뒤 쿼리의 종류와 구하는 인덱스에 따라 분기를 나누어 출력해주면 풀 수 있습니다. from collections import deque from math import log2 import sys input = sys.stdin.readline def solution(N, M, edge_li..

https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 희소 배열을 이용한 LCA 문제였습니다. 문제는 최소 / 최댓값을 구해야 하는 것입니다. 처음에는 단순히 모든 값을 비교해야 하기 때문에 기본적은 LCA 의 방식으로 하나씩 거슬러 올라갔지만 실패하고 다시 생각해야 했습니다. 희소 배열을 구성할 때 최대, 최솟값을 포함한 배열을 만들면 이 또한 빠르게 구할 수 있게 됩니다. DP 와 비슷한 개념으로 어차피..

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 백준 3584 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 dev-diary-0717.tistory.com 백준 17435 https://www.acmicpc..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net LCA 알고리즘의 개념문제입니다. 보통 희소배열 알고리즘을 통해 개선된 LCA 알고리즘을 구현하지만 이분탐색 알고리즘을 통해 구현해보고 싶었습니다. 다만 이분 탐색을 위해 모든 노드의 모든 조상을 기록하면 메모리 초과 문제가 생기므로 DFS를 통해 노드의 깊이를 잴 때 마지막 노드만의 조상을 기록했고 각 조상노드들의 최하위 노드를 기록해 조상 노..