본문 바로가기

전체 글27

BOJ 2261 : 가장 가까운 두 점 문제 링크 : 문제는 정말 단순하다. N 개의 점이 2차원 좌표평면에 있으면, 가장 가까운 두 점 사이의 거리를 구하면 된다. 단, N 제한이 최대 10만이기 때문에 O(N2) 풀이는 불가능하다. 시간을 줄이기 위해서, 우선 N2 개의 쌍들 중 답이 될 가능성이 없는 것을 생각해보자. 현재까지 구한 답이 10 이라면, x 좌표가 10 이상 차이 나는 쌍들은 답을 절대 갱신시킬 수 없다. 따라서, 현재까지 구한 가장 가까운 거리가 유용한 정보가 될 것이다. 위 논리에서 이어지는 생각으로, 우선 점들을 x 좌표 기준으로 정렬을 하자. 물론 왼쪽부터 차례대로 스위핑을 해도 되지만, 이 풀이에서는 점들을 반으로 가를 것이다. 즉 N 개의 점들을 왼쪽 N/2 개, 오른쪽 N/2 개로 분리한 후 답을 찾을 것이다... 2022. 8. 31.
Mo's Algorithm BOJ 13547 문제를 기준으로 이 알고리즘을 설명하려고 한다. 이 문제는 [L, R] 쿼리가 입력되면, A[L], A[L+1], ..., A[R] 중 서로 다른 수의 개수를 출력하는 것이다. Naive 한 풀이는 매우 쉬운데, 조금 덜 Naive 하게 생각해보자. 즉, 이전 쿼리에 대한 답을 알고 있다는 가정 하에, 현재 쿼리는 그 변화량만 계산해서 더해주면 된다. 이전 쿼리의 L, R 을 한 칸씩 움직이면서 현재 쿼리의 L, R 쿼리로 만들어준다. 이 때 숫자가 제거되거나 추가될텐데, 그에 맞게 답을 조정하는 간단한 방식이다. 하지만 이 방법 또한 O(NQ) 로 TLE가 날 것이다. Mo's Algorithm 은 오프라인 쿼리로, 이 방법을 그대로 적용하지만, 쿼리의 순서만 바꾸는 것이다. 재미있는.. 2022. 8. 29.
BOJ 3830 : 교수님은 기다리지 않는다 문제링크: 실시간으로 x, y, z 가 입력된다. 이 말은 x 보다 y 가 z 만큼 무겁다는 뜻이다. 중간중간 쿼리 a, b 가 입력된다. 이 때 우리는 a 보다 b 가 얼마나 무거운지 출력해야 한다. 샘플은 최대 10만개, 쿼리와 무게관계도 최대 10만개 입력된다. 이 문제는 개인적으로 굉장히 좋은 문제라고 생각한다. 우선 Union-Find 와 관련있다는 것은 금방 관찰할 수 있다. x y z 가 입력이 되면, x 와 y 는 서로 무게 차이를 알아낼 수 있는 관계가 된다. 그 말은, x 와 서로 무게 차이를 알아낼 수 있는 샘플은 y 와도 서로 무게 차이를 알아낼 수 있다는 것이다. 따라서 쿼리 a, b 가 입력됐을 때, a 와 b 가 연결되지 않았으면 UNKNOWN 이 답이다. 하지만 이 문제는 단.. 2022. 8. 27.
BOJ 5719 : 거의 최단 경로 문제 링크 : https://www.acmicpc.net/problem/5719 이 문제는 BOJ 1948 임계경로와 매우 유사한 문제다. 임계경로는 그래프가 DAG 이고, 최장거리를 구하는 문제여서 위상정렬 DP 로 해결하지만, 이 문제는 그래프가 일반적인 방향그래프이며, 최단거리를 구하는 문제이기에 Dijkstra 가 필요하다. 우선 최단거리에 포함되는 간선을 모두 구해야하기에, Dijkstra 역추적이 필요하다. 나는 원래 임계경로 문제를 풀 때 역추적을 비효율적으로 했었다. N개의 노드마다, 자신을 갱신시킨 노드들의 목록을 vector 로 관리했었는데, 그럴 필요가 없었다. Dijkstra 를 다 돌리고 난 후 dist 값을 비교하면 직전 노드를 직접 저장할 필요가 없다. 예를 들어, 2 -> 5.. 2022. 8. 26.
Set 와 PBDS 우리가 흔히 쓰는 std::set 은, 특정값보다 작은 원소를 세거나, K번째 원소를 구하는 작업을 O(log N) 만에 할 수 없다. 하지만, PBDS (Policy Based Data Structure) 를 활용하면 가능하다. 물론, Set 을 안 쓰고도 할 수 있다. 특정값보다 작은 원소 개수는 세그먼트 트리로 알 수 있으며, K번째 원소를 구하는 것은 세그먼트 트리 + 이분탐색으로 해결할 수 있다. 입력된 숫자 범위가 크더라도 좌표압축을 하거나, 동적 세그먼트 트리를 쓰면 될 것이다. 하지만, 위 기능들이 제공되는 Set 을 사용하면 훨씬 간단할 것이다. #include #include using namespace __gnu_pbds; #define ordered_set tree 우선 위 코드를 .. 2022. 8. 25.
CCW 에 대하여 계산기하의 기본 중의 기본이라고 할 수 있는 CCW 에 대해 알아보고자 한다. CCW는 Counter ClockWise (반시계) 의 줄임말으로, 점 3개에 대한 방향성 관계를 알 수 있는 수치다. 그림으로 보면, 세 점 A, B, C 가 2차원 좌표평면에 있다고 하자. 반직선 AB 에 대하여 점 C가 왼쪽에 있는지, 일직선 상에 있는지, 오른쪽에 있는지 어떻게 알 수 있을까? 간단한 선형대수학 내용을 알아보자. 위처럼 2×2 행렬 A가 있다고 해보자. 이 행렬 A의 행렬식 det(A) 는 아래와 같이 정의된다. det(A) 도 되고 |A| 도 맞는 표현이다. 두 대각선 원소들의 곱을 빼면 det(A)가 되는 것이다. ad < bc 라면 det(A)는 얼마든지 음수가 될 수 있다. 그렇다면, 3×3 행렬.. 2022. 8. 25.

티스토리툴바