Sparse Table
sparse table(스파스 테이블)이라고 불리는 기법이 있습니다. 이 기법에 대해 설명하는 글입니다. 예제를 통해 알아봅시다. 방향 그래프가 있습니다. 모든 점마다 나가는 화살표가 꼭 한 개씩 있습니다. 정점 하나에 말을 놓고, 이 말을 한 칸씩 움직일 거예요. 현재 있는 점에서 나가는 화살표가 한 개 있으니, 그걸 타고 새로운 점으로 갑니다. 새로운 점에서, 그 다음으로 갈 수 있는 곳도 하나밖에 없습니다. 나가는 화살표가 한 개니까요. 이렇게 나가는 화살표를 타고 계속 이동할 수 있습니다. 잘 생각해 보면, 무한히 여러 번 이동할 수 있습니다. 그렇다면 어떤 점 v에서 시작해, k번 전진했을 때 어디에 도착할까요? 이 질문에 빠르게 대답할 수 있을까요? 이런 그래프를 functional graph..
2020. 3. 2. 21:23