Algorithm/Tree2 BOJ G4 1967 트리의 지름 JAVA 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 읽기 일단 해당 문제는 트리.. 이지만 잊지 말아야 할 것은 트리도 어쨌든 그래프라는 것이다. 이 문제를 풀기 위해서 어떻게 할 지 고민하다가, 처음에는 플로이드 워샬이 생각났다. 모든 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이기에, 이를 조금 수정하면 최장 거리를 구하는 것도 할 수 있을 것이라 생각했다. 그래서 알고리즘을 다시 살펴봤는데, 시간 복잡도가 V^3이라 어림도 없었다. (해당 문제에서 V = 10000이다) 두.. 2024. 4. 6. BOJ S1 1881 트리순회 JAVA 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 읽기 해당 문제는 트리의 아주 기초적인 문제이다. 최근 트리 문제를 많이 풀지 못해서 어제 코테를 쳤는데 기초적인 트리 문제를 제출하지 못했다! 이게 너무 아쉬워서 오늘부터는 트리 문제를 중점적으로 풀어보려 한다. 문제 풀기 해당 문제에서 주어지는 트리는 이진 트리이다. 처음에 트리를 어떻게 저장할 지 고민하다가, 이전에 많이 사용했던 class 방식을 사용하기로 했다. 문제 풀이 과정은 크게 다음과 같다. 트리를 저장할 자료구조를 정의한다. 트.. 2024. 4. 5. 이전 1 다음
