- Today
- 27
- Total
- 237,967
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Archives
- 2022/06 (8)
- 2022/05 (5)
- 2022/04 (11)
- 2022/03 (11)
- 2022/02 (1)
- 2022/01 (2)
- 2021/11 (2)
- 2021/10 (2)
- 2021/09 (4)
- 2021/02 (1)
- 2020/07 (1)
- 2020/06 (6)
- 2020/05 (5)
- 2020/04 (5)
- 2020/03 (5)
- 2020/02 (6)
- 2020/01 (6)
- 2019/12 (7)
- 2019/11 (8)
- 2019/09 (7)
- 2019/06 (2)
- 2019/05 (6)
- 2019/04 (4)
- 2019/03 (8)
- 2019/02 (5)
- 2019/01 (2)
- 2018/11 (7)
- 2018/10 (10)
- 2018/09 (2)
- 2018/07 (2)
Joonas' Note
트리의 노드 순서 정리해서 구간으로 만들기 본문
제목 그대로, 트리의 노드 순서를 다시 정리하여 구간으로 표현하는 것이다.
그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다.
순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다.
이게 왜 필요할까?
제목에서 이미 말한거지만, 구간으로 표현하는 것이 더 용이할 때 사용한다.
특히 트리를 세그먼트 트리나 펜윅 트리 등의 구간합/부분합으로 변형하여 문제 해결이 필요한 경우이다.
노드의 번호를 위처럼 정리하면, 각 노드가 포괄하는 노드는 항상 확실하다.
"자신의 번호 + 그 노드의 서브 트리(들)의 크기"가 포함할 수 있는 자식의 마지막 번호와 같다.
그럼 트리를 일렬로 펴서 다룰 수 있다.
코드
관련 문제 (+스포일러)
- BOJ 2820 - 자동차 공장 : 트리를 일렬로 펴서, 각 서브 트리에 대한 변화량을 세그먼트 트리 + Lazy propagation으로 관리한다.
- BOJ 14268 - 내리 칭찬 2 : 2820번 문제와 매우 유사하다. (업데이트 범위만 살짝 다름)
- 알고스팟 - 족보 탐험 : 트리를 펴서 LCA를 구할 수 있다. 부모 노드(조상)은 항상 번호가 빠르다는 점을 이용하면 된다.
- BOJ 15899 - 트리와 색깔 : 족보 탐험 문제처럼 일렬로 펴는데, 업데이트가 없으므로 k번째 수를 찾는 문제로 쉽게 해결할 수 있다.
반응형
'알고리즘' 카테고리의 다른 글
[Graphics/Math] Euler to Quaternion, Quaternion to Euler (0) | 2022.04.05 |
---|---|
[코딩으로 풀어보기] 자동차 번호판의 숫자가 겹칠 확률 (0) | 2021.11.12 |
트리의 노드 순서 정리해서 구간으로 만들기 (0) | 2020.05.13 |
Binary search 쉬운 구현 + 설명 (0) | 2020.04.06 |
Palindromic Tree (0) | 2020.04.03 |
Rubik's Race(루빅스 레이스) 풀이 (0) | 2020.03.25 |
0 Comments