위상정렬 / Topological Sorting 유향 비순환 그래프(Directed Acyclic Graph, DAG) 에서 각 노드들을 선형 순서로 나열하는 방법입니다. 여기서 유향 비순환 그래프란, 방향이 있는 그래프 중에 사이클이 없는 그래프를 말합니다. 위상 정렬은 보통 의존 관계를 해결할 때 사용되며, 그래프 내에서 어떤 일의 순서를 정하거나 작업 간의 선후 관계를 정의하는 문제를 풀 때 유용합니다.위상 정렬의 조건그래프는 반드시 유향 비순환 그래프(DAG)이어야 합니다.유향(Directed): 간선의 방향이 있다.비순환(Acyclic): 사이클이 존재하지 않는다. 즉, 위상 정렬은 순환하는 경로가 있으면 불가능합니다.위상 정렬의 동작 원리위상 정렬의 핵심은 선행 조건을 만족하는 노드부터 순차적..

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

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

func permutation(_ target: [String], _ targetNum: Int) { var result: [[String]] = [] var check = [Bool](repeating: false, count: target.count) func permute(_ arr: [String]) { if arr.count == targetNum { result.append(arr) return } for i in 0.. 위의 코드는 메모리초과가 날 위험이 있다. let arr = ["1", "2", "3", "4"]let n = arr.countvar..