이미 구한 MST에 간선이 추가되거나 삭제됩니다. 재계산 대신 어떤 cycle·cut의 대체 간선을 찾아야 하나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

새 간선 추가는 기존 트리에 cycle을 만들 수 있어 그 경로의 가장 비싼 간선과 비교해 교체할 수 있습니다. 트리 간선 삭제는 두 성분을 잇는 최소 대체 간선을 찾아야 합니다.

기본 Union-Find는 삭제 뒤 분리와 경로 최대 질의를 해결하지 못합니다. 변경 빈도·그래프 크기에 따라 재계산과 동적 구조의 구현 비용을 비교합니다. 동점·비연결 상태의 결과 계약을 명시합니다.

이해가 드러나는 지점을 확인해 보세요.

새 간선 추가는 기존 트리에 cycle을 만들 수 있어 그 경로의 가장 비싼 간선과 비교해 교체할 수 있습니다. 트리 간선 삭제는 두 성분을 잇는 최소 대체 간선을 찾아야 합니다.
동점·비연결 상태의 결과 계약을 명시합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 새 간선 추가는 기존 트리에 cycle을 만들 수 있어 그 경로의 가장 비싼 간선과 비교해 교체할 수 있습니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.