전체 글

[위상 정렬(Topological Sort)]방향성 비순환 그래프(DAG: Directed Acyclic Graph)의 정점을 순서대로 나열하는 알고리즘입니다.상 정렬은 그래프의 각 간선 (u, v)에 대해 정점 u가 v보다 먼저 나오는 순서를 찾습니다.  위상 정렬은 DFS 기반의 방법과 Kahn's Algorithm 방법이 있습니다. 위상 정렬의 의사코드(Kahn's Algorithm)초기화:각 정점의 진입 차수를 계산하여 배열에 저장합니다.진입 차수가 0인 모든 정점을 큐에 넣습니다.큐 처리:큐에서 정점을 하나씩 꺼내서 결과 리스트에 추가합니다.꺼낸 정점의 모든 인접 정점의 진입 차수를 1씩 감소시킵니다.감소된 진입 차수가 0이 된 정점을 큐에 추가합니다.사이클 검출:결과 리스트의 길이가 정점의 총..

[최단경로 알고리즘 (Shortest Path Algorithm)] 목표: 두 정점 사이의 최단 경로를 찾는 것입니다. 이는 주로 경로 탐색, 네트워크 라우팅, GPS 경로 탐색 등에서 사용됩니다.대표적인 예시: 다익스트라 알고리즘(Dijkstra's Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm) 등이 있습니다.특징: 그래프에서 간선의 가중치를 고려하여 시작 정점으로부터 목표 정점까지의 최단 경로를 찾습니다.  최소비용 알고리즘과 최단거리 알고리즘의 차이점  목표: 최소비용 알고리즘은 모든 정점을 연결하는데 필요한 최소 비용을 찾는 것에 중점을 두고 있으며, 최단거리 알고리즘은 특정 두 정점 사이..

[최소비용 알고리즘 : Minimum Cost Algorithm)] 목표: 주어진 그래프에서 모든 정점을 연결하는데 필요한 최소 비용을 구하는 것입니다. 이는 주로 네트워크 설계, 도로망 구축, 전력 공급망 등에서 활용됩니다.대표적인 예시: 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 등이 있습니다.특징: 그래프에서 간선의 가중치를 고려하여 최소 비용으로 모든 정점을 연결하는 트리를 생성합니다.     [신장 트리(spanning tree)]신장 트리란 그래프 내의 모든 정점을 포함하는 트리입니다.신장 트리는 모든 정점들이 연결되어 있어야하고 사이클을 포함해서는 안됩니다. 신장 트리는 네트워크 구축에 많이 사용됩니다.네트워크는 각 링크마다 구축하..

[너비 우선 탐색(BFS : breath first search)]BFS(너비 우선 탐색, Breadth-First Search)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 인접한 모든 정점을 먼저 탐색하는 방식입니다. 큐 자료구조를 사용하여 구현됩니다.   BFS 알고리즘1. 시작 정점을 큐에 넣고 방문했다고 표시한다.2. 큐에서 정점을 하나 꺼내고, 해당 정점과 인접한 모든 정점을 큐에 넣고 방문했다고 표시한다.3. 큐가 빌 때까지 2번 과정을 반복한다.   BFS 구현 : 인졉 행렬#include #include #include void BFS(const std::vector>& adjMatrix, int start){ std::vector visited(adjMatrix.size(),..

[그래프의 탐색]그래프의 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다.그래프의 탐색은 매우 중요하며 크게 두 가지 방법이 있습니다. [깊이 우선 탐색(DFS : depth first search)]깊이 우선 탐색(DFS, Depth-First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 한 정점의 모든 인접 정점을 방문한 후 다음 정점으로 이동하는 방식으로 그래프를 탐색합니다. DFS는 스택 자료구조를 이용하거나 재귀 호출을 통해 구현할 수 있습니다.DFS 알고리즘1. 시작 정점을 방문하고 이를 방문했다고 표시한다.2. 현재 정점에서 인접한 정점 중 방문하지 않은 정점이 있으면, 그 정점으로 이동하여 1번 과정..

[그래프의 추상 자료형(ADT)]객체 : 정점의 집합과 간선의 집합연산 : create_graph() ::= 그래프 생성 init(g) ::= 그래프 g 초기화 insert_vertex(g, v) ::= 그래프 g에 정점 v삽입 insert_edge(g, u, v) ::= 그래프 g에 간선 (u, v)삽입 delete_vertex(g, v) ::= 그래프 g의 정점 v삭제 delete_edge(g, u, v) ::= 그래프 g의 간선 (u, v)삭제 adjacent(v) ::= 정점 v에 인접한 정점들의 리스트 반환 destroy_graph(g) ::= 그래프 g제거  [그래프의 표현 방법 - 인접 행렬]2차원 배열을 사용하여 그래프를 표현합니다.그래프의 정점..

[그래프]그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료 구조로, 많은 컴퓨터 과학 및 수학 문제에서 중요한 역할을 합니다.수학적으로는 G = (V, E)와 같이 표시합니다. 여기서 V(G)는 그래프 G의 정점들의 집합. E(G)는 그래프 G의 간선들의 집합을 의미합니다. V(G) = { A, B, C, D}E(G) = { (A, B), (A, C), (A, D), (C, D) }    [무방향 그래프와 방향 그래프] 무방향 그래프(Undirected Graph)무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다.V(G) = { A, B, C, D }E(G) = { (A, B), (A, D), (B, C), (B, D), (D, C) }   방향 그래프(Dire..

[히프 정렬(Heap Sort)]히프 정렬의 시간 복잡도는 O(n log n) 이며, 추가적인 메모리 공간을 필요로 하지 않기 때문에 제자리 정렬(in-place sorting) 알고리즘입니다.  히프 정렬 알고리즘 리스트의 원소들을 모두 힙에 넣습니다.히프의 루트의 원소를 정렬 시킬 배열에 넣고 히프에서는 제거합니다. 2의 과정을 n 번 진행합니다.   히프 정렬의 구현#include #include // 힙 정렬 함수void heapSort(std::vector& array) { int n = array.size(); // 1. 주어진 배열을 최대 힙으로 변환 for (int i = n / 2 - 1; i >= 0; --i) { siftDown(array, ..

[히프]히프(heap)는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조입니다.간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리입니다.key(부모노드) >= key(자식노드) 히프 트리에서는 중복 값을 허용한다는 것을 유의해야 합니다.  히프의 종류최대 히프(max heap) : 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다.최소 히프(min heap) : 부모 노드의 키값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다.   히프의 구현히프는 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙여서 배열의 인덱스에 넣을 수 있습니다.프로그램 구현을 쉽게 하기 위해서 배열의 첫 번째 ..

[우선순위 큐(Priority Queue)]우선순위 큐는 큐와 비슷하지만, 각 요소에 우선순위가 있어서 우선순위가 높은 요소가 먼저 나가는 자료구조입니다.  우선순위 큐의 추상자료형(ADT)객체 : n개의 element형의 우선 순위를 가진 요소들의 모임연산 : create() ::= 우선순위 큐 생성 init(q) ::= 우선순위 큐 q를 초기화 is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사 is_full(q) ::= 우선순위 큐 q가 가득 찼는지 검사 insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가 delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소 반환 find(q) ::= 우선순위가 가장 높..