PS 이야기

문제 링크 I. Robot 로봇은 초기에 동쪽을 바라보고 있고, $(0, 0)$ 위치에 있다. 회전하는 명령과 앞으로 이동하는 명령이 주어졌을 때, 주어진 정사각형 범위를 벗어나는지 아닌지 확인하고 벗어나지 않으면 최종 위치를 출력하는 문제다. 단순한 구현 문제이므로 설명은 생략한다. #include using namespace std; int yy[] = {0, -1, 0, 1}, xx[] = {1, 0, -1, 0}; int M, N; int y, x, dir; int main() { scanf("%d%d", &M, &N); for (int i=1;i M || x > M){ puts("-1"); return 0; } } printf("%d %d\n", x, y); } G. Percolation $M ..

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 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(..