[TIL] 알고리즘 : 그래프 (2)

오늘도 돌아온 이론 정리 시간 !! 이틀후면 끝이라늬 ㅜ.ㅜ

아직 난 감자이긴 한데 헤헤 구래두 팟팅팟팅

 

앞 내용 : https://lullu-nan-potato-developer.tistory.com/8

[TIL] 알고리즘 : 그래프

 

- 앞 내용 KEY WORD

• 그래프 표현 방법 : 인접리스트 >> 간선 리스트(벨만포드알고리즘) or 인접 행렬
• 서로소 집합 연산 : Union 연산 & Find 연산
• DAG : 순환 x, 방향 o, 위상정렬 가능
• 트리 : 순환 x, 방향 o, 연결 o, 정점갯수-1==간선갯수
• DST, BST
• MST 최소신장트리 : 무향 연결 그래프에 대해, 간선의 가중치합 최소인 신장트리. 구현 by 크루스칼 or 프림

 

ㅋㅋ 오늘 배운내용 찐 어렵 넘어렵 으아앙아ㅏ

 

5. 최소 공통 조상 LCA

: 정점 A와 B가 자신을 포함하여 각각 조상을 따라 거슬러 올라 갈 때, 처음 공통으로 만나게 되는 정점. 공통 조상 중 Depth가 가장 깊은 정점

 

- LCA 구하기 (효율)

1. 최상위 조상 정점을 시작으로 DFS/BFS를 수행하며 각 정점의 깊이 & 부모 정점 & 2^k번째 조상을 저장
2. 희소테이블 Sparse Table (이차원 배열을 통해) 로 구현 및 검색 => 탐색 시간복잡도 lgN (N=트리depth)
3. 검색하고픈 두 노드 A, B의 Depth를 같도록 설정 (사전에, A<=B등의 일관된 조건을 구현해놓으면 편하고 성능 굿)
4. Depth만큼 올라가며 조상 찾기 (2^n에서, n이 index = 2^n씩 점프해가며 탐색)
5. 최소 조상일때까지 찾기

parent[K][V] = parent[k-1][parent[k-1][V]

 

6. 트리에서 조상/자손 관계 판별

• in-order과 out-order 이용 (해당 정점을 방문한 순서/시간 & 해당 정점을 벗어난 순서/시간)
• 어떤 정점 A,B에 대해,  inout(A) = (in_A , out_A) , inout(B) = (in_B , out_B) 일 때
• in_A <= in_B <= out_B <= in_A : A는 B의 조상
• (in_A ~ out_A) 과 (in_B ~ out_B)의 교집합이 공집합일때 : 조상/자손 관계 아님

 

7. 단절점 찾기

- 단절점

: 무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을때, 두개의 연결 그래프로 나누어지게 하는 점

- 단절점 찾기 방법 

: 무향 연결 그래프 G에서, 어떤 정점 A에 연결된 정점들에 대해, 우회경로(A를 거치지 않는 경로)가 없는 경우가 존재하는지 확인. 존재한다면 A는 단절점

 

 

 

티스토리에 조용히 고백합니다.. 단절점 이 내용은 꽤나 minor하다는 이야기를 듣자마자 .. 정신을 놨습니다 .. 뒤늦게 따라잡아볼까했지만 .. 못알아들었숨니다 .. LCA 구현방법에 넘 몰입한 나머지 .. 하핫 핑계겠지유 .. 낼은 더 집중해서 하겟서욥

 

오늘 디게 어렵구 내용 많다 생각했는데 정리하니 .. 이거뿐이라닛 .. 그렇단 말은 코드로 구현하는게 겁나 어려웠었다는 의미..ㅎ 백준풀러가쟈 팟팅