데브카이브 데브카이브

서론최소 신장 트리(이하 MST)를 구하는 프림 알고리즘을 알아보자. 최소 신장 트리에대한 설명이 필요하다면 아래 글을 참고하도록 한다.2024.08.13 - [알고리즘] - 최소 신장 트리 최소 신장 트리신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가devchive.tistory.com 프림 알고리즘프림 알고리즘은 다음과 같은 순서를 가진다.임의의 정점을 선택해 MST에 추가한다MST에 포함된 정점과 포함되지 않은 정점을 연결하는 간선 중 가장 비용이 적은 간선을 선택해 MST에 추가한다최소 신장 트리에 V - 1개의 간선이 추가될 때 까지 2번..

서론최소 신장 트리를 구하는 알고리즘은 크루스칼 알고리즘에 대해 알아보고 관련된 백준 1197 문제를 풀어보자.최소 신장 트리에대한 설명은 아래 글을 참고하자.2024.08.13 - [알고리즘] - 최소 신장 트리 최소 신장 트리신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가devchive.tistory.com 크루스칼 알고리즘최소 신장 트리(이하 MST)를 구하는 크루스칼 알고리즘은 다음과 같은 순서를 가진다.간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다현재 선택한 간선이 정점 U,V를 연결하는 간선이라고 할 때, 만약 U..

신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가지지 않는다 위와같은 그래프가 있다고 할때 다음과같이 여러개의 신장 트리들이 나올 수 있다.  위의 예시 외에도 더 다양한 형태의 신장 트리가 존재한다.최소 신장 트리 (Minimum Spanning Tree)최소 신장 트리의 개념은 간단하다. 그래프의 존재하는 신장 트리중 가중치의 합이 가작 작은 신장 트리가 최소 신장 트리이다.위의 예시에서는 왼쪽부터 차례대로 가중치의 합이 12, 16, 18 이다. 그 외에도 존재하는 신장 트리중 가장 작은 가중치의 합을 가진 최소 신장 트리는 아래의 트리이다. ..

위상 정렬 알고리즘 위상 정렬(Topology Sort)은 순서가 있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. 위상 정렬을 하기 위해서는 사이클이 없는 방향 그래프 DAG(Directed Acyclic Graph)이여야 한다. 위상정렬은 큐와 각 노드의 진입차수(Indegree)를 이용하여 구현할 수 있다. 1. 각 Node 별로 Indegree를 구해준다. 2. Indegree가 0인 Node를 Queue에 넣어준다. 3. Queue에서 Node를 가져와 해당 Node에서 방문 가능한 Node의 Indegree를 감소시킨다. 4. 감소된 Node의 Indegree가 0 이라면 Queue에 넣어준다. 5. Queue가 빌때까지 3,4 작업을 반복한다. 위와같은 순서로 동작한다면 Queue..