문제 백준 1939번 풀이 옮길 수 있는 물건의 중량은 이어진 다리의 가중치 중 최솟값이 됩니다. 그러므로 가중치가 큰 간선(다리)을 이어주면서 공장끼리 이동 가능한지 확인하면 됩니다. 이 과정은 유사 크루스칼 알고리즘(Union-Find)을 돌리는 것으로 해결할 수 있습니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vpii; typedef vector vpll; typ..

문제 백준 16074번 풀이 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로에서 방문하는 정점 중 최대 높이를 최소화하여야 합니다. $ Q = 1 $이라고 가정하면, 높이가 $ mid $보다 작은 정점들만 사용하여 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로가 있는가 에 대한 결정 문제를 풀어야 합니다. Union-Find 자료구조를 사용하여 $ mid $보다 작은 정점들을 순서대로 합쳐주는 것은 유사 크루스칼 알고리즘을 돌려 결정 문제를 해결할 수 있습니다. 높이 $ H $에 대한 이분 탐색 $ O(log H) $, 총 정점의 개수가 $ MN $이므로 유사 크루스칼 알고리즘을 돌리는데 $ O(MNlogMN) $이 걸립니다. 쿼리..

문제 BOJ 1396번 풀이 쿼리가 하나 있다고 가정하면 아래와 같이 풀 수 있습니다. * mid보다 작거나 같은 간선들만 합쳐줍니다. (Union Find) * (쿼리) 정점 u와 v의 루트 노드가 같으면, right를 mid로 두고 그렇지 않으면 left를 mid + 1로 만들어준 뒤 계속 이분 탐색을 돌립니다. - 가중치(고유값)이 mid 이하인 간선을 이용해 정점 u, v를 포함하는 MST를 구성할 수 있냐 는 결정 문제로 볼 수 있습니다. 위와 같은 이분 탐색을 사용하면 간선을 이분 탐색하는데 $ O(log M) $, mid보다 작거나 같은 간선을 합치는데(MST를 만드는데) 시간이 $ O(M logN) $ 이고, 쿼리가 총 $ Q $개 있으니 총 시간 복잡도는 $ O (QM log N log ..

문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다. ​1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다. 시간 복잡도는 $ O(N^3) $ 가 됩니다. ​2번은 투포인터 또는 분할 정복을 사용하면 됩니다. 비슷한 문제: https://www.acmicpc.net/problem/2003​​ 3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다. 그리고 대부분이 못 푼 것 같습니다. TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsig..