PS 이야기

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 잡는다. 2. 정점 $x$에서 가장 먼 정점 $y$를 찾는다. 3. 정점 $y$에서 가장 먼 정점 $z$를 찾는다. 트리의 지름은 정점 $y$와 정점 $z$를 연결하는 경로다. 증명) 트리에서 정점 $u$와 정점 $v$를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 $x$를 정하고, 정점 $x$에서 가장 먼 정점 $y$를 찾았을 때, 아래와 같이 경우를 나눌 수 있다. i. $x$가 $u$ 혹은 $v$인 경우 ii. $y$가 $u$ 혹은 $v$인 경우 iii. $x$, $y$, $u$, $v$가 서..

문제 링크 I. Q-Index $n$개의 논문들에 대한 인용횟수가 주어지고, $k$번 이상 인용된 $k$편의 논문이 있고, 나머지 $n-k$편의 논문은 모두 인용횟수가 $k$이하일 때, Q-Index는 $k$라고 얘기한다. 가능한 Q-Index 중 가장 큰 값을 구하는 문제다. 매우 쉬운 문제라 0이상 $n$이하의 $k$를 정한 뒤, 실제로 $k$가 Q-Index가 되는지 확인하는 $O(n^2)$ 방법과 인용횟수 배열을 내림차순으로 정렬한 뒤에 이를 더 빠르게 계산하는 $O(n \lg n)$ 방법 두 가지가 있다. #include using namespace std; int N; int A[1001]; int main() { scanf("%d", &N); for (int i=1;i= i){ printf(..

문제 링크 E. 닉네임에 갓 붙이기 $N$개의 닉네임이 음절 단위로 쪼개져 주어진다. 첫 음절을 제외하고, 맨 앞에 "god"을 붙여 출력하는 문제다. 줄 별로 입력받고 입력 받은 문자열을 공백으로 나누어 문자열 배열로 만들어주면 된다. C, C++에서 이는 strtok 함수를 통해 간단히 해결할 수 있다. #include using namespace std; int T; char buf[999]; int main() { for (scanf("%d ", &T);T--;){ fgets(buf, 997, stdin); bool sw = 0; printf("god"); for (char *pt=strtok(buf, " \n\r");pt;pt=strtok(0, " \n\r")){ if (sw) printf(pt..