03-07 학습&숙제

03-07 학습! 위상 정렬! 선수과목!🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔😭⭐

위상 정렬🟥

유향 그래프의 정점들을 변의 방향 (간선의 방향)을 거스르지 않도록 나열하는 것!

순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘

대표적인 예시 선수과목 구조!

선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다

정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.

위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하면 안된다!

비순환 유향 그래프여야 한다.

결과🟧

위상 정렬이 가능한지 여부 - 사이클 발생 여부 확인 가능

가능하다면 정렬된 결과

방법🟨

BFS를 이용한 구현이 쉽다 😎

0. 정점들의 진입차수 계산 - 전처리
1. 진입 차수가 0인 정점(시작 정점)을 큐에 모두 넣는다.
2. 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다.
   -> 인접한 정점의 진입 차수를 1 감소시킨다.
3. 간선 제거 후 진입 차수가 0이 된 정점을 큐에 넣는다.

큐가 공백 큐 상태가 될 때까지 2-3 작업을 반복한다.
하나 처리할 때 마다 카운트를 세어서 정점의 갯수와 일치하면 사이클 없이 위상 정렬 완성
🫢정점의 갯수와 일치하지 않으면 사이클 발생! 위상정렬 실패!

강사님 수업🟩

Topology 🟦

그래프에서 인접행렬로 표현한 다음에

행마다 합을 구해준다

그러면 전입이 몇번이 되었는지 파악 가능!

그래서 0인 것을 큐에 넣고 간선 제거 하고 다시 큐에 넣고

가장 보편적인 것은 각 정점마다의 진입차수 배열과 인접리스트 그래프 구현 후 BFS 돌리기!

효율적인 해킹 변형 if DAG 🟪

만약 dag 일때 가장 긴 것을 구하라

DAG는 방향 사이클(directed cycle)이 없는 방향 그래프를 의미

숙제 🟫

SQL-D 시험 통과하기