문제 링크
- http://icpc.me/2583
이전 글에서 소개했던 0-1BFS알고리즘과 함께 찾은 특정한 그래프에서 작동하는 다익스트라 알고리즘을 발견하게 되어서, 이 알고리즘도 소개를 합니다.
어제 알고리즘에 대해 검색을 하다가 코드포스 블로그에서 흥미로운 최단경로 최적화법을 찾아서, 그 방법을 소개하고자 합니다.
세그먼트 트리는 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조입니다.
이진 트리의 형태를 띄고 있으며 naive한 방식보다 훨씬 효율적으로 작업을 처리할 수 있습니다.