My life story

1. 문제 링크 www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 2. 문제 개요 N개의 정점으로 이루어진 트리가 있다. (트리 : connected acyclic undirected graph ) 정점은 1번부터 N번까지 번호가 매겨져 있다. 두 개의 쿼리를 수행하는 프로그램을 작성하자. (1) 1 u v : u에서 v로가는 경로의 비용을 출력한다. (2) 2 u v k : u에서 v로 가는 경로에 존재하는 정점 중 k번째 정점을 출력하자. 3. ..

1. 문제 링크 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 2. 문제 개요 루트가 있는 트리가 주어지고, 트리의 간선들이 주어진다(부모 자식 관계). 그리고 마지막으로 LCA를 찾을 두 노드가 주어진다. 주어지는 두 노드의 LCA를 출력하는 프로그램을 작성하시오. 3. 문제 힌트 첫 번째로 루트를 찾자. 부모 -> 자식 방향으로 간선이 존재한다고 했을 때, 루트는 어떻게 찾을 수 있을까? 두 번째로 L..

1. 문제 링크 www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 2. 문제 개요 각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다. 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가한다. 노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y사의의 거리를 ..

여러 자료를 참조하면서 LCA를 공부했는데, 어떤 자료는 너무 쉽고 깔끔하지 못하고, 어떤 자료는 난이도가 있고 깔끔하게 설명된 자료였습니다. 그래서 여러 자료를 찾아보며 이해하고, 또 이해하느라 조금 복잡했는데, 하나의 블로그에서 LCA의 개념부터 구현까지 공부할 수 있으면 어떨까 해서 기록을 합니다. 개념에 대해서 알아보고, 백준(BOJ)의 간단한 LCA문제를 풀어보면서 글을 마치겠습니다. 다른 분들에게 도움이 되었으면 좋겠습니다. 1. LCA란? 참조(en.wikipedia.org/wiki/Lowest_common_ancestor) 'In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w i..