목록최소신장트리 (1)

미새문지

크래프톤 정글 week02, day12 - 위상정렬, B-Tree, 트라이, 최소 신장 트리

위상정렬 수서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 답이 한 가지가 아니라 여러 가지가 존재할 수 있고 DAG(Directed Acyclic Graph)에만 적용이 가능하다. DAG는 사이클이 발생하지 않는 방향 그래프이며, 사이클이 발생하면 위상정렬을 수행할 수 없다. 위상정렬은 두 가지 해결책을 낼 수 있는데 현재 그래프가 위상정렬이 가능한지, 위상정렬이 가능하면 그 결과는 무엇인지이고 스택과 큐를 이용해 알고리즘을 짤 수 있다. 진행 과정(큐를 사용) 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선 제거 3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때 까지 2번, 3번 과정 반복. 모..
크래프톤 정글/TIL 2024. 2. 19. 14:00
이전 Prev 1 Next 다음