| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- JavaScript
- 벨만-포드
- PROJECT
- 비트필드를 이용한 dp
- ccw 알고리즘
- 2-SAT
- Strongly Connected Component
- Github
- Binary Lifting
- reference counting
- Delete
- 자바스크립트
- Prisma
- SCC
- Overlapped Model
- DP
- 강한 연결 요소
- Behavior Design Pattern
- select 모델
- 그래프 탐색
- Lock-free Stack
- Spin Lock
- 트라이
- 비트마스킹
- 최소 공통 조상
- trie
- 게임 서버 아키텍처
- HTTP
- 이분 탐색
- map
- Today
- Total
목록Binary Lifting (2)
dh_0e
도로 네트워크 (백준 3176번) LCA 2(백준 11438번)처럼 희소 배열을 이용한 최소 공통 조상(Binary Lifting) 알고리즘을 활용한 문제. [PS] LCA 2 / C++ (백준 11438번)희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfdh-0e.tistory.com구현이 꽤 복잡하지만 설계를 잘 하고, LCA를 적절하게 구현하면 쉽게 풀 수 있다. #include#include#includeusing namespace std;vector> vec[100001];int depth[100001],..
LCA 2 (백준 11438번) 희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfs()함수로 트리를 만들며 각 node들의 parent 정보를 희소 배열에 저장하는데 이때, 희소 배열을 2차원으로 parent[i][j]=i번째 node에서 $2^j$번째 부모를 저장하는 방식으로 만들어준다. N 2. depth 배열을 만들어 각 node들의 깊이 또한 저장해준다. 주요 식은 다음과 같다.parent[i][j]=parent[parent[i][j-1]][j-1]; 3. 다음 입력받은 두 노드의 깊이를 맞춰준다. 이때, 2..