CP Algorithm & Knowledge (31) 썸네일형 리스트형 플로이드 워셜 알고리즘 파헤치기 (초안이 2025. 08. 28에 작성된 포스트이며 내용이 더 추가될 수 있습니다. 내용이 충분히 채워졌다고 판단하면 이 내용은 지워집니다.) 플로이드 워셜 알고리즘은 세간에서 $O(N^{3})$으로 전체 쌍의 최단 경로를 구할 수 있는 알고리즘이라고 단순하게 알려져 있다. 그렇다고 단순하게 구현 코드를 외우고 있으면 피를 본다. 콘테스트, 코딩테스트에서 출제 빈도가 은근히 낮아 원리를 까먹기 쉬운데, 까먹고 있는 상태에서 응용문제를 만나면 바사삭 깨지는 일이 일어나곤 한다. 그래서 이 포스트에서는 플로이드 워셜 알고리즘을 원리부터 이해해 가면서 여러 심화 응용문제를 통해 의문사를 예방해 보도록 하자.플로이드 워셜의 핵심 아이디어와 코드플로이드 워셜의 아이디어는 정점 집합 $\{1, 2,..., k\}.. LIS와 multiset 사실 이게 뭔진 모르겠지만 나 스스로 뭔가 흥미로운 방법으로 문제를 풀고 있는 것 같아 기록해둔다. 일단 이 문제를 보자. https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의를 모두 진행할 수 있는 회의실의 최소를 구하는 것이다. 나는 이렇게 풀었다. 1. 빨리 끝나는 순서로 정렬한다. 끝나는 순서가 같으면 시작하는 시간이 빠른 순서로 정렬한다. 2. multiset을 준비한다. 첫 번째 회의는 trivial case로 두어 첫 번째 회의.. pb_ds의 간단한 고찰 - 트리 구현체 PS를 좀 오래 한 사람이라면 pb_ds의 존재를 알고 있을 것이다. 그리고 보통 트리의 구현체로 r-b 트리인 rb_tree_tag를 쓸 것이다. 하지만 r-b 트리 외에도 스플레이 트리 구현체인 splay_tree_tag가 존재한다. C++ 상에서 구현된 r-b 트리는 상수가 크다고 알려져 있는데 그럼 스플레이 트리를 대신 쓰면 성능이 좀 좋아질까? 그래서 해보았다. 백준 2104 - 스플레이 트리 http://boj.kr/1404da72672b4c429dfc8f2504ff4558 백준 2104 - r-b 트리 http://boj.kr/b9c4a1b73379447192b2c6153f223525 무려 스플레이 트리가 2배 더 빠르다! 그러면 다른 문제로 확인해보자. 백준 1572 - 스플레이 트리 ht.. 2차원 평면에서 모든 점 쌍의 유클리드 거리 합 구하기 오늘은 이런 문제를 풀어보자. 2차원 직교 좌표계에서 N개의 점이 있다. ($N \leq 10^{6}$) 좌표가 동일한 두 점이 존재할 수 있다. i번째 점을 $p_{i}$라 하고 i번째 점과 j번째 점의 유클리드 거리 제곱을 $dist(p_{i}, p_{j})$라고 했을 때 다음을 구하시오. $\sum\limits^{N - 1}_{i = 1}\sum\limits^{N}_{j = i + 1} dist(p_{i}, p_{j})$ 지금 생각할 수 있는 간단한 방법은 $\binom{N}{2}$의 쌍의 거리를 일일이 계산하는 것이다. 하지만 그런 걸로 되면 이 글을 쓸 필요도 없다. N이 100만까지 갈 수 있으므로 컴퓨팅으로는 빠른 계산이 당연히 어렵다. 이 포스트에서는 이 문제를 무려 $O(N)$에 풀어볼 .. Dynamic Segment Tree and Lazy Propagation 이 포스트에서는 다이나믹 세그먼트 트리에 대한 소개와 레이지 프로퍼게이션까지 구현을 해보도록 한다. 엄청 큰 범위에서의 구간 쿼리? 다음 문제를 해결한다고 해보자. 수열 a가 있을 때 1. ai에 x를 더한다. 2. i > 1; auto lval = tree[tree[node].l].val; if (lval >= kth) return kth_query(tree[node].l, from, mid, kth); return kth_query(tree[node].r, mid + 1, to, int(kth - lval)); } Colored by Color Scripter cs 이 함수를 가지고 4번 쿼리를 처리하면 된다. 일기 예보를 해결하는 전체 코드는 다음처럼 짤 수 있다. 노드 개수를 주의하자. 1 2 3.. 이전 1 2 3 4 ··· 7 다음
