티스토리 뷰

DS\Algo

BOJ 11932 트리와 K번째 수

MathTrauma 2022. 8. 26. 13:36

 

문제 링크 : https://www.acmicpc.net/problem/11932 

 

11932번: 트리와 K번째 수

첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두

www.acmicpc.net

 

persistent segment tree + lca 로 해결했다. (더 나은 방법은 없을까?)

lca 를 위한 dfs 를 거치면서 부모 노드가 각 자식노드를 생성하는 segment tree 이다.

 

최소공통조상(lca)는 아래 글에서 간략히 정리해 두었으니 참조.

BOJ 3584 Nearest Common Ancestors

 

BOJ 3584 Nearest Common Ancestors

주어진 문제는 root 가 주어진 tree 에서 최소(?)의 공통 조상을 찾기를 요구하는데... 노드(정점) 집합의 크기로 보아 lca(least comman ancestor) 와 관련된 기술을 쓰지 않아도 될 것으로 보인다. 하지만

mathtrauma.tistory.com

 

persistent segment tree는

BOJ 13537 수열과 쿼리 1 (Persistent Segment Tree version)

 

BOJ 13537 수열과 쿼리 1 (Persistent Segment Tree version)

수열이 모두 입력되고 나서 쿼리가 따로 주어지므로 소위 off-line query로 해결하라는 거 같은데... 익숙해지면 persistent segment tree 가 구현하기 오히려 편하게 느껴진다. persistent segment tree는 배열의.

mathtrauma.tistory.com

 

에서 언급한 바 있다.

추가적으로 따로 설명할 새로운 개념은 없다.

 

 

 

 

 

반응형

'DS\Algo' 카테고리의 다른 글

BOJ 11405 책 구매하기  (0) 2022.08.29
BOJ 2316 도시 왕복하기 2  (0) 2022.08.26
BOJ 17408 수열과 쿼리 24  (0) 2022.08.25
BOJ 13537 수열과 쿼리 1 (오프 라인 쿼리 version)  (0) 2022.08.17
BOJ 2208 보석줍기  (0) 2022.08.16
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/05   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함