내용 정리 (3) 썸네일형 리스트형 [알고리즘] Dijkstra 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로는 하나의 시작점이 정해져있을 것, 그리고 음수 값을 가진 간선이 없을 것이다. Greedy 적인 방법으로 접근하기 때문에 음수 값의 간선이 존재하면 알고리즘이 성립하지 않는다. 자세한 설명들은 다른 블로그에 잘 나와있으니까.. 헷갈릴 만한 개념들만 되짚어보자. 진행 방향은 다음과 같다. 초기조건 : 일차원 Distance를 저장할 수 있는 배열(이하 Dist[]). 무한대에 비슷한 큰 값을 넣어준다. 시작 집합에 시작점을 넣어준다. 알고리즘 : 1. 시작집합과 연결된 노드 중 가장 거리가 짧은 노드(이하 a).. [C++] STL heap 예제로 간단히 정리하기 아래는 heap djikstra인데 오름차순 정렬해주는 heap을 사용하였다. 자동으로 O(logn)에 정렬해주기 때문에 매우 유용하다. #include #include #include #include #include #define INF 99999999 using namespace std; int n,e; int s; struct tuple2 { int node; int val; }; struct pq_tuple { int idx; int dist; bool operator node.dist; } }; vector A[20005]; long long dist[20005]; int visited[200.. [C++] STL sort 시간복잡도 : O(n*logn) 추가해줘야할 헤더 : #include 사용법 : sort(A,A+n); (구조체, 배열) sort(A.begin(),A.end()); (vector 형식) #include #include #include using namespace std; int n; struct tuple2 { long long s,e; }; tuple2 A[100000+5]; bool sf(tuple2 a,tuple2 b) { if(a.e==b.e) { return a.s 이전 1 다음