sparse table (1) 썸네일형 리스트형 165. Sparse Table 희소 테이블(Sparse Table)은 정점마다 나가는 간선이 하나씩 존재하는 유향 그래프에서 사용할 수 있는 자료 구조로 어떤 정점에서 간선을 따라 여러 번 이동했을 때 어떤 정점에 도착하는지를 빠르게 구할 수 있다. 가끔씩 희소 배열(Sparse Array)이라고 표현하기도 하지만 이 단어는 다른 뜻이 많아 혼동하기 쉬워서 잘 쓰이지 않는다. 다음과 같은 그래프가 있을 때 정점 $\text{D}$에서 간선을 따라 $4$번 이동하면 정점 $\text{C}$에 도착한다. 각 정점에서 간선을 따라 이동했을 때 도착하는 정점을 이동 횟수에 따라 표로 나타내면 다음과 같다. $0$ $\text{A}$ $\text{B}$ $\text{C}$ $\text{D}$ $\text{E}$ $\text{F}$ $\text.. 이전 1 다음
