티스토리 뷰
문제 링크 : 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
- shell
- map
- C++ big number
- max flow
- javascript array
- math font
- BOJ
- RUBY
- fenwick tree
- lazy propagation
- dynamic programming
- 다익스트라
- Dijkstra
- python3
- 세그먼트 트리
- Vim
- JavaScript
- 백준
- Shell Programming
- bash script
- Reference
- 정수론
- segment tree
- Aho-Corasick
- persistent segment tree
- stack
- bash
- nearest common ancestor
- script
- number theory
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |