분류 전체보기 (26) 썸네일형 리스트형 BOJ 18193번: 비행기 타고 가요 개요 - 알고리즘 분류: Dijkstra, Merge Sort Tree, Segment Tree Lazy Propagation - 문제에 대한 평가: 2차원을 관리하는 효과적인 자료구조에 대한 시사점을 제공함. 아이디어가 기발함. 구현이 상당히 많음. 문제 요약 N개의 정점이 있는 그래프에서 간선 M개가 다음과 같이 주어진다. (cost, s1, s2, e1, e2): 모든 s1 이상 s2 이하의 정점에서 모든 e1 이상 e2 이하의 정점으로 가는 가중치 cost의 간선이 있다. V에서 각 정점까지의 최단 거리를 구하라. 문제 풀이 과정 먼저, s1을 인덱스로 삼고 s2에 대해 정렬하는 Merge Sort Tree를 만든다. Dijkstra를 수행하되, 티켓을 정점으로 생각한다. 이때 (e1, e2)로 .. PS에 사용되는 C++ 기능 정리 C++의 Standard Template Library에는 C언어보다 훨씬 많은 함수와 기능들이 있기 때문에, 이들을 모두 익히는 것은 불가능하다. 하지만 PS에 사용되는 함수와 자료구조들은 굉장히 한정적이다. 이에 이들을 간략히 정리하고자 한다. 다른 사람들도 볼 수 있게 해서 문제를 풀다가 필요한 기능에 해당하는 C++ 함수를 찾아볼 수 있도록 하고, 나도 가끔씩 C++의 함수가 헷갈리기 때문에 정리해 두고 참고용으로 사용하기 위함이다. 나는 C++ 언어 자체는 깊게 모르고, PS에 사용되는 기법들만 익히는 정도이기 때문에, 이론적인 내용에는 오류가 있을 수 있으며 오류를 발견하면 댓글로 달아주면 감사하겠다. iterator 객체지향형 프로그래밍 언어인 C++의 가장 큰 특징은 class와 templ.. 이전 1 2 3 4 다음