Algorithm/Tree

[SW Expert Academy 1248번] 공통 조상

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 공통 조상 문제는 크기 두 개의 과정이 필요합니다. 공통 조상 찾기 서브 트리 크기 계산 공통 조상 찾기는 아래의 과정으로 구할 수 있습니다. a 정점의 모든 부모 노드를 구한다. b 정점의 모든 부모 노드를 구한다. 이분 탐색을 위해 b 정점의 모든 노드를 정렬한다. a에 가까운 조상부터 b 정점의 조상 노드에 포함되어 있는지 확인한다. 서브 트리 크기 구하기는 아래의 과정으로 구할 수 있습니다..

[백준 20955번] 민서의 응급 수술 (C++)

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 민서의 응급 수술 문제는 BFS/DFS를 이용하여 해결할 수 있습니다. 모든 뉴런을 하나의 트리 형태로 연결하기 위해서는 흩어져 있는 각각의 그래프가 모두 트리여야, 연결했을 때 트리 형태를 유지할 수 있습니다. 모든 뉴련을 하나의 트리 형태로 연결하기 위한 연산으로, 아래의 두 가지 연산이 있습니다. 두 뉴런을 연결한다. 이미 연결된 두 뉴런의 연결을 끊는다. 트리는 정점이 N개 일 때, N..

[백준 15681] 트리와 쿼리 (C++)

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 알고리즘의 기본 틀은 아래와 같습니다. BFS 수행 후, 각 정점의 부모 노드를 찾음. BFS를 수행하면서 Leaf 노드는 서브 트리 크기를 1로 설정 각 정점의 서브 트리의 크기를 구함 서브 트리의 크기 = 자식 서브 트리의 합 + 1 재귀와 memoization를 이용 전체 코드는 아래와 같습니다. #include using nam..

[백준 4803번] 트리 (C++)

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 트리 문제는 그래프와 BFS를 이용하여 해결할 수 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 트리의 방문하지 않은 각 정점부터 시작하여 BFS를 수행 인접한 정점이 이미 방문했지만, 부모 노드가 아닌 경우 싸이클이 존재한다고 판단. 따라서, 트리가 아니라고 판단. 인접한 정점이 이미 방문하였고, 부모 노드인 경우 방문을 진행 아래는 전체 코드입니다. #include usi..