Algorithm1 오일러 경로 테크닉(Euler Tour Technique) 오일러 경로 테크닉 (Euler Tour Technique) ETT라고도 불리는 이 테크닉은 DFS를 이용한 트리 관련 테크닉입니다. 구체적으로는, 어떤 트리가 있을 때, 해당 트리에 속한 노드 N과, 노드 N을 루트로 가지는 서브트리에 속한 모든 노드들을 하나의 연속된 구간으로 표현할 필요가 있을 때 사용됩니다. 음, 이를 좀 다르게 말해보면, 일반적인 트리를 세그먼트 트리로 변환시킬 때 필요한 테크닉입니다. 방법에 대해서는 이 글에서 설명할 예정이지만, 결론부터 말하자면, 트리의 각 노드들에 구간 [DFS 함수가 시작된 시점, DFS 함수가 종료된 시점]을 부여해주면 됩니다. 이런 모양의 트리가 있습니다. 이제 이 트리에 대해서 오일러 경로 테크닉을 사용해볼텐데, 그전에 먼저 트리의 순회 방법부터 정.. 2022. 10. 12. 이전 1 다음
