03-05 학습 & 숙제

03-05 학습! 🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔😭⭐

그래프😎

정점, 간선, 차수

V개의 정점을 가지는 무향 그래프는 최대 V(V-1)/2 간선이 가능 ⭐
유향 그래프는 V(V-1) 간선 가능!

그래프 유형 🔔

트리도 그래프! -> 트리의 조건을 만족하면 두 노드간의 경로는 유일하다! ⭐⭐

그래프 표현

인접 행렬 - 2차원 배열 이용

인접 리스트 - 각 정점마다 다른 정점으로 가는 정보 저장

간선 리스트 - 시작 정점, 끝 정점의 정보를 묶어서 리스트에 저장
간선을 하나씩 소비하고 싶을 때 필요 -> MST의 크루스칼 (프림은 정점 중심)

강사님 수업 🤔

MST (모든 정점)

간적쿠 , 간만프

쿠르스칼 ⭐

s,e,w 로 노드를 만들고 comparable 해서 pq의 유니온 파인드

프림 ⭐

인접리스트 중심 얘도 pq를 이용한다
적은 정점을 찾아서 작은 간선을 찾는다 그래서 두개가 이어지면 두개를 다 간선을 이어준다. 이렇게 계속해서 퍼트려주는 느낌
특징 : 아무 정점에서 시작해도 괜찮다! , 다익스트라와 코드가 95프로 동일
구현 : V와 E를 인접리스트를 구현하고 visited가 필요!

유니온 파인드 ⭐

아이디어 : 보스를 구하기!
처음에는 자기가 보스인데 누군가의 밑으로 들어가기
보스가 하나일때까지 붙이면 전부다 연결되었다
랭크를 활용하면 평균 속도 유지가능

숙제

이제 3월 8일까지 sqlD 올인합시당