위상 정렬 알고리즘 (Topology Sort) 위상 정렬은 방향성이 있는 유향 그래프에서 순서가 정해져있는 정점들의 순서를 거스르지 않으면서 모든 정점을 나열하는 알고리즘입니다. 위상 정렬의 대표적인 예시는 다음과 같습니다. 예를 들어 컴퓨터공학과에서 알고리즘 과목을 수강하고자 할 때 해당 과목을 수강하기 위한 선수 과목들이 존재합니다. 즉, 알고리즘을 수강하기 위해선 자료구조를 먼저 수강해야 하며 C프로그래밍을 수강하기 위해서는 먼저 이산수학을 수강해야 할 것입니다. 순서가 존재하는 유향그래프에서 위 예시를 위상 정렬하면 다음과 같은 순서가 나타납니다. 이산수학 -> 프로그래밍 원리 -> C프로그래밍 -> 자료구조 -> 알고리즘 위상 정렬을 통해 올바른 수강순서를 찾아낼 수 있습니다. 이처럼 선후 관..

데이크스트라 알고리즘 (Dijkstra Algorithm) 데이크스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 탐색 알고리즘입니다. 예를 들어 여러 개의 도시가 있을 때 도시 사이를 연결하는 도로의 길이를 최소 비용으로 계산하여 건설하고자 할 때와 같이 현실 세계의 다양한 상황에서 사용될 수 있는 알고리즘입니다. 또한 그래프 내에서 하나의 최단 경로는 다른 여러 최단 경로로 만들어질 수 있으므로 기존에 저장되었던 최단 경로의 결괏값이 그대로 사용될 수 있다는 점에서 다이나믹 프로그래밍을 적용하여 사용할 수 있습니다. 알고리즘 원리 위 그림에서 정점 1로부터 정점 2, 3, 4로의 최단 경로가 각각 5, 9, 13으로 설정되어 있습니다. 정점 1은 방문이 완료되었으므로 다음으로 가장 가까운 정점..

그래프(Graph) 표현 그래프의 표현 방법에는 인접 행렬, 인접 리스트, 인접 배열이 존재합니다. 인접 행렬(adjacency matrix) 방법 간선 (i, j)가 존재하면 원소(i, j) = 1을 저장하며 그렇지 않으면 원소(i, j) = 0이 됩니다. 정점의 총 개수가 N이라고 할 때 인접 행렬은 N X N 행렬입니다. 무방향 그래프의 경우 대각선 행렬을 중심으로 대칭적이지만 방향 그래프의 경우 반드시 대칭적이지 않고 비대칭일 수도 있습니다. 또한 가중치가 있는 그래프의 경우 원소(i, j)는 1 대신에 가중치를 저장합니다. 인접 리스트(adjacency list) 방법 정점의 총 개수가 N이라고 할 때 각 정점에 인접한 정점들을 N개의 연결리스트로 표현한 방법입니다. i번째 리스트는 정점 i에 ..

그래프 Graph 그래프는 객체 간의 관계를 표현하는 자료구조입니다. 지도에서 지점들의 연결 상태, 도로망, 과목 선후수 관계, 전기회로의 소자 간 연결 상태, 사람들 간의 친분 관계 등을 그래프로 표현할 수 있습니다. 즉, 그래프란 현상이나 사물을 정점(vertex)과 간선(edge)로 표현한 것입니다. 그래프의 정의는 G = (V, E) 로 주어지며 V는 정점 집합, E는 간선 집합입니다. 정점(vertex) 객체를 의미하며 노드라고도 불립니다. V(G) : 그래프 G의 정점들의 집합을 의미합니다. 간선(edge) 정점들간의 관계를 의미하며 링크(link)라고도 불립니다. E(G) : 그래프 G의 간선들의 집합을 의미합니다. G1과 G2는 무방향 그래프, G3는 방향 그래프입니다. 방향성 존재 여부에..