[⭐항상 새겨두어야할 공부 방법⭐]
- 다른 사람한테 설명 가능해야 함! (설명 못하면 제대로 이해 못한거)
- 항상 구조적으로 생각하고 이해하기 ( 왜 이렇게 되는지 )
- 하고 많은 다양한 똑같은 것들 중에서 왜 이걸 사용하는지?
Nest.js 를 공부하다가 본 내용인데 Nest에서 "모듈 이벤트는 위상 정렬(Topological Sort)을 거쳐 거리에 따라 정렬된 후, onModuleInit를 호출한다" 라고 해서 위상정렬이 뭔지 한번 찾아봤다!!
위상정렬은 쉽게말해서 "순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해서" 사용하는 알고리즘이다!
- 위상 정렬은 여러가지 답이 존재할 수 있다!
- DAG(Directed Acyclic Graph)에만 적용할 수 있음..! << 사이클이 존재하지 않는 그래프
두 가지 해결책을 낸다는 특징이 있음!!
1. 현재 그래프는 위상 정렬이 가능한지?
2. 만약에 가능하다면 그 결과는 무엇인지?
두가지 알고리즘
1. Stack 을 이용한 방식
2. Queue 를 이용한 방식 << 더 많이 사용됨
🔸위상정렬 순서!
1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다!
3. 간선을 제거한 후에 진입차수가 0인 정점을 큐에 삽입한다!
4. 큐가 빌 때까지 2~3 과정을 반복. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다!!
- 각 정점별로 진입차수를 배열에 넣어준다
- 진입차수가 0인 것을 큐에 넣는다.
- 큐에서 꺼낸 다음 연결된 간선 제거 --> 각 정점의 진입차수 갱신
- 다시 갱신된 진입차수 배열을 가지고 진입차수가 0인 것을 큐에 넣는다
- 위 내용을 반복,,!
⭐ 동빈나님 유튜브 보고 참고함..!
우선 러프하게 이해하고 정리를 해봤는데 코드도 짜보고 해야겠다!
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
이건 풀어보자 ㅎ
