목록트리 (1)

알고리즘 일지

BOJ 23054 - 누텔라 트리 (Hard)

문제 링크BOJ - 23054 : 누텔라트리 23054번: 누텔라 트리 (Hard) boj.ma  문제 풀이 신나게 떠들던 와중, 이 문제를 알게 되어 잡게 되었다. 푸는데 한달정도 걸렸다.나는 이 문제를 EulerTour Tree (ETT)로 풀었다. 즉, 독자분들이 대부분 아는 EulerTourTrick (ETT) 와는 다른 별개의 굉장히 하드코어한 알고리즘을 다룬다. EulerTourTree 는 SplayTree를 사용하여, 간선을 관리하는 자료구조 이다. EulerTour경로를 순서대로하여, 이용한 간선과 그 방향을 순서대로 다 저장하는 방법을 사용한다. 굉장히 어려운 알고리즘이다.이 알고리즘을 응용하여 풀어 볼 수 있는 문제로는 27974번: 트리와 쿼리 21 가 있다. 오일러투어트리의 구현에 ..
알고리즘 풀이 2024. 5. 21. 00:23
이전 Prev 1 Next 다음