루오구 P2537 스키 문제: 유향 그래프에서 최소 신장 트리 활용 전략
루오구 P2537 스키 문제는 여러 산봉우리 중 1번 산에서 출발하여, 자신보다 낮은 산으로만 스키를 타고 이동할 수 있습니다. 또한, '물약'을 사용하여 이전에 방문했던 어떤 산으로든 되돌아갈 수 있습니다. 이 문제의 목표는 1번 산에서 도달 가능한 모든 산을 방문하는 데 드는 최소 총 비용을 계산하는 것입니다.
문제 분석 및 접근 방식
스키를 타는 것은 높은 산에 ...
11월 5일 10:18에 게시됨
유니온 파인드 - 강의 내용 보완 (진행 중)
작업 중...
여기서 유니온 파인드 템플릿을 먼저 제공합니다.
다음은 일반적으로 사용되는 두 가지 형태입니다.
경로 압축
int parent[MAXN], n, m;
void init() {
for(int i = 1; i <= n; i++) parent[i] = i;
}
int root(int x) {
if(x != parent[x]) parent[x] = root(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int rx = root(x) ...
10월 13일 09:31에 게시됨
자료구조 문제 풀이 모음
이 문서에서는 다양한 자료구조 문제들을 다루며, 세그먼트 트리, 블록 분할, 그리고 코뜰리 트리(ODT)를 활용한 풀이를 소개한다.
P6812 「MCOI-02」조상 (Ancestor)
문제에서 정의한 "조상"은 비내림차순 수열이다. 이를 판별하기 위해 차분 배열을 활용하여 세그먼트 트리로 구간 최솟값을 관리할 수 있다. 차분 배열의 구간 최솟값이 0 이상이면 해당 구간은 비내림차 ...
6월 12일 16:42에 게시됨