목록분류 전체보기 (105)
yoongrammer
목차 벨만-포드 알고리즘(Bellman-Ford Algorithm) 알아보기 벨만-포드 알고리즘 (Bellman-Ford Algorithm)은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다. https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로 yoongrammer.tistory.com 특징 brute force str..
목차 다익스트라 알고리즘 (Dijkstra's Algorithm) 알아보기 다익스트라(Dijkstra) 알고리즘은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다. https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로 yoongrammer.tistory.com 특징 음수 가중치를 가진 간선이 없어야 합니다. 탐욕 알고리즘..
목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로를 말합니다. 경로 p = 의 가중치(w) 합이 다음과 같다면 $$ w(p) = \sum_{i=1}^k w(v_{i-1},v_{i}) $$ 정점 u에서 v까지의 최단경로 값은 다음과 같이 표시합니다. $$ \delta(u,v) = \begin{cases} min\{w(p) : u \overset{p}\rightsquigarrow v \}, & \mbox{if u에서 v로 가는 경로가 있다면} \\ \infty, & \mbox{if u에서 v로 가는 경로가 없다면} \end{case..
목차 위상 정렬(Topological sort) 개념 및 구현 비순환 방향 그래프 (DAG: Directed Acyclic Graph) Directed Acyclic Graph (DAG)는 사이클이 없는 방향 그래프입니다. DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용됩니다. 위상 정렬(Topological sort) 위상 정렬(Topological sort)은 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것입니다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 됩니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다. 그래프에 사이클이 있으면서 두 정점 u,v가 사이클 속에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v..
목차 그래프 순회 (Graph traversal) 알아보기 그래프 순회(traversal)는 모든 정점을 방문하는 작업입니다. 그래프는 탐색하는 동안 동일 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(Visited)했다는 표시를 하여 중복 방문을 피하도록 합니다. 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색 (DFS: Depth First Search) 너비 우선 탐색 (BFS: Breath First Search) 깊이 우선 탐색 (DFS: Depth First Search) 깊이 우선 탐색 (DFS: Depth First Search)은 그래프에서 최단 경로를 찾는 간선 기반 알고리즘입니다. DFS는 형제 정점을 ..
목차 그래프 표현 및 구현 그래프는 일반적으로 두 가지 방식으로 표현합니다. 인접 행렬 (adjacency matrix) 인접 리스트 (adjacency list) 인접 행렬(adjacency matrix) 인접 행렬은 그래프를 2차원 배열에 저장하는 방법입니다. 부속된 간선을 찾는 것은 빠르지만 |V| x |V| 만큼의 공간이 필요하여 저장 측면에서 비효율적입니다. (|V| : 정점 수) 노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용합니다. 각 행과 열은 정점을 나타냅니다. 1. 방향성 그래프 (Directed Graph) 방향성 그래프를 인접행렬로 표현하면 다음과 같습니다. 각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장..
목차 그래프 (Graph) 알아보기 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다. 정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말함. 간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍 (u, v)로 표현함. 그래프(G)는 정점들의 집합 V와 간선들의 집합 E를 사용하여 (V, E)로 나타냅니다. G = (V , E) V = {1, 2, 3, 4, 5} E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)} 그래프 용어 Directed edge & Undirected edge 방향성(유향) 간선 (Directed edge) 방향을 가진 정점의 쌍 (u, ..
목차 해시 테이블 (Hash Table) 알아보기 해시 테이블(hash table)에 대해 알아보기 전에 Direct address table에 대해 알아보도록 하겠습니다. Direct Address Table Direct address table은 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다. Direct address table은 키 k가 테이블 slot T[k]에 저장되기 때문에 테이블의 크기는 전체 키(U) 개수가 됩니다. 위 특징 때문에 direct address table은 중복 키가 없고, 테이블의 크기가 작은 경우에 사용할 수 있습니다. 구현 방법 전체 키 집합(U = {0,1 ... ,9})의 크기만 한 테이블(T)을 배열로 만듭니다. 실제 사용하는 키 집합(K = ..
목차 우선순위 큐 (Priority Queue) 개념 및 구현 일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다. 하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다. 우선순위 큐는 다음과 같은 속성을 가지고 있습니다. 모든 항목에는 우선순위가 있습니다. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다. 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됩니다. 4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같습니다. (여기서 높은 값이 높은 우선순위..
목차 힙 (Heap) or 이진 힙(binary heap) 알아보기 힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조입니다. 힙은 다음과 같은 속성을 가지고 있습니다. 완전 이진트리(Complete Binary Tree) 이다. 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다. 키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음. 힙의 종류 힙에는 두가지 종류(최대 힙, 최소 힙)가 있습니다. 1. 최대 힙 (Max Heap) 부모 키값이 자식노드 키값보다 큰 힙 Key(parent) ≥ Key(child) ..