PS 이야기

ICC $N$개의 정점으로 이루어진 그래프가 있다. 그래프의 초기 상태에는 간선이 하나만 존재한다. 두 정점 집합 사이에 간선이 있는지 묻는 질문을 통해 간선이 무엇인지 알아낸다. 알아낸 이후에 새로운 간선이 또 추가된다. 항상 싸이클이 생기지 않도록 간선이 주어지며, 이 작업을 총 $N-1$번 수행하고 질문을 가능한 적게해야하는 문제다. 처음 상황, 즉, $N$개의 정점이 있고 그들 사이에 간선이 하나만 있는 상황에서 생각해보자. 우선 간선을 가지고 있는 임의의 두 정점 집합을 최대한 적은 질문안에 찾아야한다. 이는 최대 $\lceil\lg N\rceil - 1$번 질문만에 찾을 수 있다. 바로 각 정점 번호를 0번부터 N-1번까지 나타낼 때, 각 비트에 대해 비트값이 0인 집합과 비트값이 1인 집합 ..

2차원 좌표 평면에 정수 좌표 (x, y)로 이루어진 서로 다른 점 $N$개가 있다고 하자. 이 점들 중 유클리드 거리계에서 가장 먼 두 점을 $O(N \lg N)$ 시간복잡도로 구할 수 있다. Claim 1) 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리 중 최대값이 가장 먼 두 점의 거리다. 증명) $N$개의 점들 중 가장 먼 두 점을 $a$와 $b$라 하자. $a$와 $b$를 잇는 선분을 그리고 수직한 직선을 그렸을 때 아래와 같이 된다. 파란색 직선 위를 포함하여 파란색 영역에 $a$와 $b$ 이외에 다른 점들은 존재하지 않다. 만약 존재한다고 가정하면 $a$와 $b$가 가장 먼 두 점이라는 가정에 모순된다. 따라서 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양..

처음 배열에서 힙을 구성할 때 선형시간으로 구성하는 방법이 있다. 일반적으로 각각의 원소를 삽입하는 방식으로 힙을 구성하면 자명하게 $O(N \lg N)$ 시간복잡도를 갖는다. 이를 $O(N)$에 해결할 수 있는 방법을 설명하겠다. 힙의 모양을 구성한 뒤에 맨 아래 정점부터 처리하는데, 부모 정점의 값보다 자신의 값이 우선순위가 더 높다면 부모 정점의 값과 자신의 값을 바꾼다. 이 뒤에 자신의 값의 우선순위가 자기 자식 정점의 값보다 낮을 수 있으므로 마찬가지로 재귀적으로 확인해준다. 이렇게 진행될 경우 아래에서 $h$ 높이에 있는 정점을 처리할 때, 최대 $h$번의 swap이 일어날 수 있다. 이를 수식으로 써서 나타내면 연산회수의 상한은 $n \times \sum{\frac{h}{2^{h-1}}}$ ..