코딩테스트 - 패스트캠퍼스 챌린지 35일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 위상 정렬

학습 후기
위상 정렬: Directed Acyclic Graph(DAG)
1. 간선에 방향성이 있다.
2. 사이클이 없다.
3. 그래프로 정점과 간선을 가진다.
차수(degree)란 정점에 연결된 간선의 개수
방향성(Directed)은 Indegree / Outdegree로 구별
정점들을 위상에 맞게 정렬

위상 정렬 해당 문제 - 제일 먼저 올 수 있는 정점은?
들어오는 간선이 없는 정점이다.
정렬 방법
1. 정점들의 Indegree를 계산한다.
2. 들어오는 간선이 0개인 정점을 찾아서 자료구조에 넣는다.
3. 자료구조가 빌 때까지
1) 자료구조에서 원소 X를 꺼내서 정렬한다.
2) 그래프에서 정점 X를 제거한다.
3) 새롭게 정렬 가능한 점을 찾아서 자료구조에 넣는다.
정점들의 Indegree를 계산할 때 주어진 문제에서 간선들을 돌아가며 확인하면 되므로 O(E)만큼의 시간 복잡도가 필요하다. 자료 구조에 필요한 연산은 원소를 추가하거나 꺼내는 함수가 필요하므로 해당 함수에 시간 복잡도가 O(1)인 Queue를 사용하여 구현한다. 자료구조가 빌 때까지 원소 X를 꺼내서 정렬하고 제거하고 새롭게 정렬 가능한 점을 찾아서 D에 넣는데 이때의 시간 복잡도는 자료구조가 비어있는지 while문을 사용하여 계속 확인하고 정점이 한 번씩 들어오기에 O(V)에 정점을 제거할 때마다 모든 정점을 돌면서 간선이 삭제되어 있는 걸 확인해야 되기 때문에 총 O(V^2) 번의 시간 복잡도가 필요하게 된다. 하지만 위상 정렬에서 원소를 제거하고 indegree를 계산할 때 0이 되는 정점만 새롭게 정렬 가능한 점이 만들어지게 되며 이를 수정하면 시간 복잡도 O(E)까지 구할 수 있다. 그래서 위상 정렬의 총 시간 복잡도는 O(V + E)라는 걸 알 수 있다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.