개발윗미

[위상 정렬이란 ?] 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 위상 정렬 알고리즘 학습 시 진입차수(Indegree)와 진출차수(Outdegree)가 존재하는데, 진입차수는 특정한 노드로 들어오는 간선의 개수이고, 진출차수는 특정한 노드에서 나가는 간선의 개수이다. 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다. 1. 진입차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. (1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. (2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 3. 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 구..

[신장 트리란 ?] 신장 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. [크루스칼 알고리즘이란 ?] 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류가 되며, 동작 과정은 다음과 같다. 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 만약, 사이클이 발생하지 않는다면 최소 신장 트리에 포함시키고, 사이클이 발생한다면 최소 신장 트리에 포함시키지 않는다. 3. 모든 간선에 대하여 2번의 과정을 반복한다. 구체적인 동작 과정은 아래의 게시물에서 확인할 수 있다. https://unie2.tistory.com/37?category=873806 크루스칼 ..

이분 매칭은 집단이 존재할 때 A 집단이 B 집단을 선택하는 방법이다. 아래와 같이 숫자 집단과 알파벳 집단이 있다고 가정하고, 1번은 알파벳 A, B, C 를 선택하고 2번은 알파벳 A를, 3번은 알파벳 C를 선택했다고 할 때 이분 매칭은 모든 숫자가 각각의 알파벳을 선택하여 가장 많이 연결되는 경우를 탐색할 수 있도록 한다. (1) 먼저 알파벳 A가 아무 번호에도 연결되어 있지 않기 때문에 1번이 알파벳 A를 선택한다. (2) 2번이 A를 선택하는데 A는 1번에 연결되어 있기 때문에 A를 점유하고 있는 1번부터 다시 출발하여 A를 제외하고 다른 곳에 연결될 수 없는지 확인한다. (3) 1번은 알파벳 B에 연결될 수 있기 때문에 B에 연결하고 2번은 A에 연결한다. (4) 3번이 B를 선택하는데 B는 ..

위상 정렬은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 주의할 점은 위상 정렬은 사이클이 발생하지 않는 방향 그래프 즉, DAG(Directed Acyclic Graph)에만 수행이 가능하다. 왜냐하면 위상 정렬은 기본적으로 시작점이 존재해야 하는데 사이클 그래프에서는 시작점부터 찾을 수 없기 때문이다. 위상 정렬을 수행하는 과정은 아래와 같다. 정점 1 2 3 4 5 6 7 진입차수 0 1 1 1 1 2 1 여기서 진입차수는 해당 정점에 들어오는 간선의 수이다. 즉, 정점6은 정점4와 정점5에서 간선이 들어오기 때문에 진입차수가 2이다. 또한, 정점1은 들어오는 간선이 없기 때문에 진입차수는 0이다. (1) 진입차수가 0인 정점1을 큐에 삽입한다..

플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프가 존재할 때, 각각의 정점이 다른 정점으로 가는 거리(비용)을 2차원 배열로 나타내면 아래와 같다. 0 5 INF(무한) 8 7 0 9 INF(무한) 2 INF(무한) 0 4 INF(무한) INF(무한) 3 0 위 표는 현재까지 계산된 최소 비용이며, 이러한 2차원 배열을 반복적으로 갱신하여 모든 최소 비용을 구하는 과정은 아래와 같다. (1) 노드 1을 거쳐가는 경우 [ 2->3 ] 노드 1을 거쳐가야 하기 때문에 1을 포함하지 않은 경우들만 계산해주면 된다. 0 5 INF(무한) 8 7 0 [ 2->3 ] [ 2->4 ] 2 [ 3->2 ] 0 [ 3->4 ] INF..