경로 및 서브트리 갱신을 위한 Heavy-Light Decomposition 활용
이 문제는 트리 위에서 두 가지 쿼리를 처리해야 하는 고전적인 HLD(Heavy-Light Decomposition) 적용 문제입니다. 노드 구간의 지연 갱신과 서브트리 합 질의를 효율적으로 해결해야 합니다.
핵심 개념
트리를 선형 구조로 변환하여 구간 자료구조를 적용하는 것이 핵심입니다. DFS 순서를 활용하면 서브트리를 연속된 구간으로 표현할 수 있으며, Heavy-Light Decomposi ...
8월 1일 09:05에 게시됨
NOIP 2024 시뮬레이션 경연 문제 분석 및 구현 가이드
철도 2 (Railway 2)
트리 구조에서 모든 노드 쌍 사이의 거리 함수 $f(i,j)$의 총합을 구하는 문제입니다. 이 문제의 핵심은 특정 노드에서 출발할 때 트리의 지름(Diameter) 끝점 중 하나로 향하는 경로가 최적의 해를 포함한다는 점입니다.
트리의 지름을 구한 뒤, 두 끝점을 기준으로 각 노드까지의 거리를 계산하여 정렬합니다. 이를 통해 각 노드별 기여도를 계산하여 ...
7월 13일 22:29에 게시됨
스위핑 라인(Sweep Line) 알고리즘 이해하기
스위핑 라인은 데이터 구조를 활용한 중요한 기법으로, 주로 구간 내 부분 구간의 정보를 쿼리하는 문제를 해결할 때 사용됩니다. 이 기법은 오프라인 처리 기반으로 동작합니다.
기본 아이디어는 다음과 같습니다. 모든 쿼리를 오프라인으로 저장한 후 특정 기준으로 정렬합니다. 그런 다음 배열의 시작부터 끝까지(1부터 n까지) 순회하면서 정보를 점진적으로 업데이트 ...
7월 6일 20:02에 게시됨
NOIP 모의 경연 1 회 후기 및 문제 분석
서론
올해도 역시 AC 자동기 문제에서 고배를 마셨다. 사실 ST3 문제에서 AC 자동기 접근 방식이 매우 자연스럽게 떠올랐고, 절반 정도는 해결했음에도 불구하고 T4 문제로 방향을 틀어 결국 300점 이상의 고득점을 놓치고 말았다. Trie 트리와 실패(Fail) 포인터가 어쩌면 운명적인 조합처럼 느껴지지 않는가? 최종 결과는 100 + 100 + 20 + 0으로 아쉬운 성적으로 마무리 ...
7월 3일 18:18에 게시됨