반응형 Algorithm/알고리즘2 [알고리즘] 위상정렬 위상정렬 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 위 그림에서 3가지 일을 다 할 수 있는 방법은? 1회초 -> 1회말 -> 2회초 (o) 1회초 -> 2회초 -> 1회말 (x) 특징 - 다양한 답이 존재 - DAG(directed acyclic graph: 방향이 있고 사이클이 존재하지 않는)에만 적용 가능 - 그래프는 위상 정렬이 가능한지, 가능하다면 결과는 무엇인지를 판단할 수 있다 스택과 큐 두 가지 방법으로 가능하지만 큐를 추천한다. 알고리즘 동작 과정 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거 3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때까지 2,3 과정을 반복한다.. 2023. 5. 27. [알고리즘] 크루스칼 알고리즘 크루스칼은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘으로 가장 적은 비용으로 모든 노드를 연결하기 위해 사용한다. 즉 노드를 연결해 모든 노드가 다 연결되게 할 때 제일 적은 비용을 사용하는 방법을 찾는것이다. 예를 들어 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결할 때 최소한의 비용으로 하는 알고리즘 노드=정점=도시 -> 그래프에서 동그라미 부분 간선=거리=비용 -> 그래프에서 선에 해당하는 부분 최소비용신장트리의 간선숫자는 노드숫자 -1이다 위 그래프에서 노드는 7개, 간선은 10개, 최소비용신장트리의 간선 숫자는 6개이다 크루스칼 구현 과정 1. 모든 간선 정보를 오름차순으로 정렬 2. 비용이 적은 간선부터 사이클이 발생 안 한다면 차근차근 그래프에 포함. 사이클이 발생하면 .. 2023. 5. 22. 이전 1 다음 728x90
