다익스트라 정리 다익스트라 풀이처음에 다익스트라로 n까지 최단 거리 구함. (구하면서 prev에 간선 정보들을 저장)prev를 이용하여 graph에서 해당하는 간선들을 삭제.다시 다익스트라를 돌려서 n까지 가는 최단 거리를 구함.고려한 점도시는 양방향으로 이동할 수 있다. (최단거리라면 양방향 둘 다 막힌다)다른 도시로 이동할 때 코스트가 다른 도로가 존재할 수 있다 ( 1->2 (1), 1->2 (2)) 이때 cost 가 1인 도로만 막힘탈출하지 못하는 경우는 없다.정답 코드더보기#include using namespace std;#define INF 1e9void dijkstra(int n, vector>>& graph, vector& distance, vector& prev..

다이나믹프로그래밍과 다익스트라 두 방법 모두 사용할 수 있습니다. 시간 복잡도시간 복잡도는 O(D + N)입니다.D는 고속도로의 길이, N은 지름길의 수입니다.문제에서 N ≤ 12, D ≤ 10,000이므로, 이 접근 방식은 충분히 효율적입니다. C++ DP 풀이.#include using namespace std;#define INF 1e9int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d; cin >> n >> d; vector> graph[10001]; for (int i = 0; i > from >> to >> cost; if (to dist(d + 1, INF); dist[0] = 0; for (int ..

다익스트라 알고리즘 / Dijkstra's algorithm다익스트라 알고리즘은 단일 출발점 최단 경로를 찾는 알고리즘입니다. 가중치가 음수가 아닌 그래프에서 출발점에서 모든 다른 정점까지의 최단 경로를 구할 때 사용됩니다. 다익스트라 알고리즘은 우선순위 큐(Priority Queue)를 이용해 최단 거리가 가장 작은 정점을 빠르게 탐색하여 최적화된 성능을 제공합니다.다익스트라 알고리즘의 특징음의 가중치 간선 허용 안 함: 음의 가중치가 있는 그래프에서는 올바르게 작동하지 않습니다.우선순위 큐 사용: 최단 경로를 더 효율적으로 찾기 위해, 가중치가 가장 작은 정점을 빠르게 선택하기 위해 우선순위 큐(최소 힙)을 사용합니다.시간 복잡도: O((V + E) * log V) - 여기서 V는 정점의 수, E는 ..

세그먼트 트리에 대해서 알아보고 해당하는 자료구조에 대해서 코드로 어떻게 사용하는지에 대해서 정리하려고 작성하였습니다.https://book.acmicpc.net/ds/segment-tree자세한 설명은 위의 백준북에서 볼 수 있습니다.  C++#include using namespace std;using ll = long long;ll init(vector &a, vector &tree, int node, int start, int end);ll sum(vector &tree, int node, int start, int end, int left, int right);void update(vector &tree, int node, int start, int end, int index, ll diff);..

처음 접근 - 벨만 포드 벨만 포드 풀이 시간초과 코드 보기.더보기이유. O(V * E) 벨만-포드 알고리즘의 시간 복잡도는 **O(V * E)**입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다.주어진 문제에서:N (정점의 수) = 최대 300,000M (간선의 수) = 최대 1,000,000따라서 벨만-포드를 사용했을 때 최악의 경우 시간 복잡도는:O(V×E)=O(300,000×1,000,000)=300,000,000,000O(V \times E) = O(300,000 \times 1,000,000) = 300,000,000,000O(V×E)=O(300,000×1,000,000)=300,000,000,000즉, 300조의 연산을 수행해야 합니다. import Foundation let I..