트리의 지름 2

트리의 지름을 구하는게 공식이 있다니... (#1167)

#1167 트리의 지름 https://www.acmicpc.net/problem/1167 문제를 풀이하는 과정이 너무 복잡했다. (결국 블로그 참고함) 다음 세 가지를 배울 수 있었다. 1. DFS 구현의 두 가지 방식(재귀 vs 스택)의 장단점결론부터 말하면, 스택으로 구현해야 메모리를 덜 사용한다.재귀로 짰더니 계속 메모리 초과가 났다. 2. 비트마스크로 visited를 처리하는 방법기존의 리스트나 셋을 사용해서 노드 방문 여부를 체크하는 것과 달리 비트마스크로 구현하면 메모리 사용량을 줄일 수 있다.쉽게 생각하면 기존에 [ 0, 1, 0, 1, 0, ... ] 이렇게 저장하던 visited 0/ 1을 그냥 붙여서 이진수로 표현하는 것이다.Ob01010... 되게 심플하다.따라서 원하는 인덱스 만큼 ..

처음 구해본 트리의 지름 (골드3을 이해하기 시작하는 중)

#1167번 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 문제이다. 대충 거리의 총합정도는 구하겠는데 어떻게 최대거리를 갖는 노드를 찾는지 도저히 이해가 되지 않았다. 다음 블로그를 참고했다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름..

728x90