목록최소공통조상 (1)

전자공학 및 알고리즘

백준 11437 - LCA(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 최소 공통 조상을 물어보는 문제였습니다. 연결된 노드가 주어졌을 때, 두 노드의 최소 공통 조상을 구하는 문제입니다. 문제에서 N과 M이 크기 때문에, 조상을 구하는 과정을 반복하면 시간초과가 생기게 됩니다. 따라서 트리를 만든 뒤, 깊이를 통해 조상을 구하는 방식을 사용해야합니다. 트리를 만드는 코드입니다. void make_tree(){ queue q; q.push(1)..
백준 2023. 4. 25. 23:25
이전 Prev 1 Next 다음