어제 알고리즘에 대해 검색을 하다가 코드포스 블로그에서 흥미로운 최단경로 최적화법을 찾아서, 그 방법을 소개하고자 합니다.

처리해야 할 쿼리

이전 글에서는 다음 두 가지 쿼리가 주어졌습니다.

1. 구간 [l, r]이 주어졌을 때 해당 구간의 합 구하기
2. i번째 수를 v로 바꾸기

Segment Tree란?

세그먼트 트리는 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조입니다.
이진 트리의 형태를 띄고 있으며 naive한 방식보다 훨씬 효율적으로 작업을 처리할 수 있습니다.

문제 링크

• https://www.acmicpc.net/problem/4008

문제 링크

• http://icpc.me/15885

문제 링크

• http://icpc.me/15885

문제 링크

• http://icpc.me/15889

문제 링크

• http://icpc.me/15888

문제 링크

• http://icpc.me/15886

이 알고리즘은 출발점부터 도착점까지의 최단 경로(정확히는 최단 경로에 근접한 결과)를 알아내는 알고리즘입니다.