다익스트라 알고리즘 / 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..

Bellman–Ford algorithm 벨만-포드 알고리즘벨만-포드(Bellman-Ford) 알고리즘은 그래프에서 음의 가중치를 허용하면서 단일 출발점 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과는 달리 음의 사이클을 탐지할 수 있는 특성 때문에 특정 문제들(예: 네트워크에서 음의 가중치가 있는 경로 등)을 해결하는 데 유용합니다.벨만-포드 알고리즘의 특징시간 복잡도: O(V * E), 여기서 V는 정점의 개수, E는 간선의 개수입니다. 따라서, 다익스트라보다 느리지만 음의 가중치를 포함할 수 있다는 장점이 있습니다.음의 가중치: 음의 가중치를 허용합니다. 다익스트라와 달리, 음의 사이클이 있을 때도 탐지할 수 있습니다.음의 사이클 탐지: 벨만-포드는 그래프에 음의 사이클이 존..

c++17을 기준으로 사용합니다.아래 레퍼런스를 참고하였습니다. C++17 - cppreference.comThe following features were merged into C++17: From the File System TS: the filesystem library. From the Library fundamentals v1 TS: features, including std::any, std::optional, std::string_view, std::apply, polymorphic allocators, searchers. From Libraryen.cppreference.com C++Clang++ 10.0 (C++17)clang++ -std=c++17 -O2 -Wno-unused-resul..