weekly ps

Table of Contents 개요방법 1 - 동적계획법방법 1 코드방법 2 - 탐욕법방법 2 코드방법 2 의 정당성방법 2 로 far 배열 찾기문제 1. 개요 트리의 지름이란, 트리 내에서 가장 먼 두 정점 사이의 거리를 뜻합니다. 이 글에서는 트리의 지름을 구하는 2가지 방법에 대해 소개합니다. 참고로 이 두 가지 방법은 모두 시간 복잡도를 늘리지 않는 선에서 'far [ v ] = 정점 v와 v에서 가장 먼 정점 사이의 거리'를 모든 정점에 대해 구할 수 있습니다. far 배열을 구하면 지름 = MAX(far [ v ])로 쉽게 구할 수 있으며, 지름만 구할 때 보다 더 다양한 상황에 쓸 수 있게 됩니다. 때문에 이 문서에서는 far [ v ] 을 구하는 방법까지 소개하도록 하겠습니다. 방법 1은..