Greedy 수업 필기

26.

그래프 용어 (참고: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html)

비방향성 그래프

->양방향 통행 도로를 생각

->엣지를 통해서 양 방향으로 갈 수 있다. 

->ex) 정점 a와 정점 b를 연결하는 엣지는 (a,b)와 같이 정점의 쌍으로 표현한다. (a,b)와 (b,a)는 동일 

방향 그래프

->일방 통행 도로를 생각

->엣지에 방향성이 존재하는 그래프

27.

신장트리란?

->'부분'그래프

->

&G안에 모든 정점을 포함하며

&트리가 되는

(임의의 노드에서 다른 노드로 가는 경로가 유일, 회로가 존재하지 않는다, 모든 노드는 서로 연결, 엣지를 하나 자르면 트리가 두 개로 분리, 엣지의 수는 노드의 수에서 1을 뺀 것과 같다)

(connected and undirected graph with no cycle)

&연결된 

29.

최소비용신장트리란? (MST)

->최소의 비용을 가지고 모든 점들이 연결되도록 하는 방법을 구할 때 최소 비용 신장 트리 문제라고 한다.

->가능한 신장트리 가운데 엣지 가중치의 합이 최소인 신장트리를 말한다. 

->노드 간 연결성을 보장하며 노드 사이를 잇는 거리/비용 등을 최소로 하는 그래프를 의미하기 때문에 응용 범위가 넓다. 

====================================1025

32.

MST 알고리즘1. 무작정 알고리즘. 

-신장트리는 부분 그래프. 그래프에서 나올 수 있는 신장트리의 경우의 수 다 구해보고 거기서 MST찾기

worstcase-지수승 정도 나오는데 안좋음

각 노드마다 넣냐/마냐를 해야함. 

edge가 많을수록 더 심각. 

모든 edge에대해서 포함시키냐/마냐 의 2가지씩 생각해야 함. 

O(n제곱)

만약 노드 수가 n개라면 최대 edge수는 (모두 연결되어 있는 경우) 2분의 n에 n+1이다. 

더 좋은 방법 없나? 

최소/최대라는 단어가 언급됨 -> 그리디로 해볼까? 

33. 6분 32초 (그리디 방법)

이미 예전에 만들어진 알고리즘이 있음. prim과 kruskal. 

프림:

크루스칼:

목적: 그래프에서 엣지들 부분을 찾는데, 트리가 되는, 비용이 최소가 되는 것을 찾자. 

어느 엣지를 찾아서 트리를 만들고 최소를 만드냐? =mst 찾자

순간 순간 좋냐를 물어보고(feasibilty검사) 좋으면 포함 그 다음 것 선택. 반복. 

(b) feasibility:'선정한'- 어떻게 선정? 가장 좋은 것 선정. 

하지만 프림스와 크루스컬은 뭐가 좋은지 바라보는 관점이 다름

크루수칼: edge의 weight가 가장 적은 것을 고름. edge관점에서 봄. 엣지를 다 늘여놓고 disconnected되던 안되던 줏어담고 cycle없이 줏어담다보면 어찌됐든 연결이 될테니. 

프림: 아무 arbitrary 노드를 정함. 점에서부터 하나하나 연결시켜나감. 노드를 하나씩 붙여나가는. 노드에 연결된 가장 작은 엣지가 뭘까. 그 순간 이 점에서 가까운 것을 찾는 (그리디 맞음)

둘 중 뭐가 좋은지는 단정지을 수 없음. 어떤 문제냐에 따라 프림스가 나을 수 있고 크루스칼이 나을 수 있음. 

--------------------------------프림 크루스칼 요약 정리 출처: http://stack07142.tistory.com/54 [Hello World] 

- 프림과 크루스칼 알고리즘은 최소 스패닝 트리를 구하는 방법 중 하나이다.

- 둘 다 Greedy Method을 기초로 하고 있다. (당장 눈앞의 최소 비용의 선택을 해서 결과적으로 최적의 Solution을 찾는다.)

- 프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘이다.

- 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않지만

- 크루스칼은 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하면서 MST를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야 한다. 사이클을 확인하는 방법으로는 Union-Find(Disjoint-Set) 방법이 있다.

- 시간 복잡도는 비슷하지만, 일반적으로 Dense한 그래프의 경우 프림이, 그렇지 않은 경우에는 크루스칼이 유리하다.

- 프림의 경우 최소 거리의 정점을 찾는 부분에서 자료구조의 성능에 영향을 받는다.

- 크루스칼은 간선을 weight 기준으로 정렬하는 과정이 오래 걸린다.

- 프림 : O(V^2+E) → O(E logV)

- 크루스칼 : O(E logE)

--------------------------------

35. 프림스 16분 11초

프림스 크루스칼 설명: http://eehoeskrap.tistory.com/39   

-> 프림 예시 꼭 해보기

예시 해볼 떄 주의 

-> 사이클 생기면 폐기

-> 후보군은 노드에 연결된 모든 엣지. 

-> 노드가 꼬리에 꼬리를 물고 항상 이어지는 것이 아님. 

-> 엣지 수가 정점보다 1개 적으면 중단하기. 

이해한 후에

36

(영어) 코드 흐름 읽어보기 

====================================1030

37

nearest-가장가까운노드가 들어있음. 

ex) a와 가장 가까운 노드가 c이면 배열 첫 번째에 c가 들어있음.

distance - 그 노드의 edge의 거리(=weight/가중치)가 들어있음 

ex)a와 c의 edge가 3이면 배열 철 번째에 3이 들어있음. 

38-40

ex) arbitraty vertex를  3으로 정함. 

nearest [5,6,4,2,1]

distance [35,15,20,25,10]

업데이트 해서 배열 계속 바뀌고.

->전체 노드를 다 보지 않고 nearest와 distance만 봄. 

만약 5를 선택했을때 

nearest( 6,   3->2)

6번노드와 2번노드 중 가까운 거리가진 노드를 가지고 비교한 다음 더 가까운 거로 선택해서 뻗어나가면 됨 (15 vs 40) 15 선택. 6과 3 연결

반복.

사이클 생기면 버리고

반복된것은 또 선택할 수 없으니 세컨드인 애로 결정 

이렇게 업데이트하면서 반복

distance(35->40)

전체 노드가 연결될 때까지 함. (for loop이니까)

프림 알고리즘: http://makefortune2.tistory.com/37

41

분석

n: 노드의 갯수다. 

항상 분석할 때 n이 무엇인지 알고 있어야 함 (시험때도 적어두기)

O(n제곱)

이유???????????????????????????????????????????????다시보기

42 크루스칼 (프림스보다 좀 더 간단함)

edge(=연결선)들을 순서대로 새움. 비내림차순(숫자가 작은 순서대로)으로

for loop반복 - edge 수 만큼 반복 

선정 절차: 연결선 결정

feasibility검사: 사이클이 생기는지 아닌지 

해보기: https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

-> 일단 weight를 작은 것부터 나열해놓고,

-> 작은 weight를 가진 두 노드를 연결해봄.

-> 연결하며 그림. 그리면서 사이클 생긴다면 다음 가중치로 넘어감. 

-> 노드가 N개 있다면 EDGE가 N-1개일 때까지 반복하고 스탑

43

1. edge들을 순서대로 정렬

2. edge수만큼 for loop 

사이클 생기냐 안생기면 집어넣고 생기면 버리고 

끝

훨씬 간단. 

노드 제일 작은 10 선택, 그 다음 15 선택, 사이클 안생김 넘어감. 그 다음 20 선택. 25 선택. 사이클 안생김. 30 선택. 사이클 생김. 30 버림. 35 선택. 사이클 안생김. edge 다 봤으므로 끝. 

운 안좋으면 edge들 다 볼 수 있음. 

44 분석

sort하는데 걸리는 시간 : 만약 merge sort 썻다면(제일 좋은 거) nlogn -> 이 때 n은 edge의 갯수. 프림과 헷갈리지 않게 n이 아닌 e에 대한 식으로 표현. 즉, eloge로 표현.

 

for loop안에서는 사이클 생기냐 안생기냐를 검사. -> 이것도 시간이 걸리겠지만  e보다 작아서 무시 

=>결국 걸리는 시간은 eloge

[프림과 크루스칼 시간 복잡도 요약]

프림스 n제곱. 여기서 n은 노드의 갯수 

크루스칼 eloge. 여기서 e는 edge의 갯수 

=>크루스칼이 좋다고 바로 말할 수 없음. 왜냐면 n과 e는 다름. n이 엄청 작다면 프림스가 더 좋음. 

=>n과 e의 관계에 따라 뭐가 더 좋은지가 달라짐

 

그럼 어떻게 비교? 왜 두 개 다 비교? 

노드와 edge의 관계는? 

edge의 밀도가 엄청 좁으면 프림스가 더 낫고 헐렁헐렁하면 크르수칼이 더 나음 

=>이렇게 input값에 따라 달라지므로 두 개를 같이 배움  

47

최단 경로: 제일 짧은 경로

기준:(예를 들어 통학에 대한 거라면) 시간이 짧은 거? 제일 적게 갈아타는 거? 무엇을 기준으로? 

shortest path=>하나의 기준을 잡아서 제일 짧은 경로를 찾는 것

single source=> 시작은 한 지점에서만 시작한다는 뜻.  

single source shortest path=> 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것을 의미한다. 

49

https://www.zerocho.com/category/Algorithm/post/584bd46f580277001862f1af

기본으로 깔고 가는 조건: 모든 정점의 최단 거리 값을 infinity(무한)으로 설정

      시작점 최단 거리값을 0으로 설정

      시작 점 거리값에 weight 값을 더한 것보다 도착점 거리값이 크면 도착점 거리값을 더한 값으로 낮춘다. 

시작점에서 제일 짧은 애를 일단 선택

그 선택한 애를 거쳐 가는게 좋은지 vs 시작점에서 제일 짧진 않지만 다른 애를 선택하는 게 낫나 -> 이것을 dist에 계속 업데이트 

연결이 안되어있으면 무한대 

가장 짧은 s와 t의 거리를 dist(t)라고 하고 t에서 v1의 거리를 더함 

=====================================1101

49

예시로 설명

예시) a-2-b-5-c

a-3-d-1-c

a-8-c

가장 가까운 노드와의 거리는 t라 함 

t에서 v1/v2등등 까지

dist와 w 차이 

51-59

19분

source 아무거나로 시작해도 되지만 여기는 v1으로 둠

첫 째줄 step 1

둘 째줄 step 2

dist를 다시 계산. min을 구해서 업데이트 

표 보면 최단 거리는 알 수 있지만 어디를 거쳐서 오는지는 알 수 없음

알게하려면 앞의 코드를 바꾸면 됨 min이 업데이트 될 때마다 노드를 적어주면 됨  (숙제로 내줄 예정) 

 세로줄 보면 무한대에서 1/7로 줄어듬. 그 과정에서 v1을 거쳤다는 것을 알 수 있음. 

7에서6, 무한대에서 5, 무한대에서 4로 줄어듬. 더 좋았기 때문에 줄어든 것임. v2를 거쳤다는 것을 알 수 있음. 

6에서5. 또 줄어듬. v5를 거쳤다

5에서5. 안 줄어듬. v5를 거치지 않았음을 알 수 있다. 

51쪽 예제 다시 해보기 !!!. 헷갈림 주의 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!

->연결된 노드 다 확인했는지 보기 

->시작점과 weight 숫자 값 헷갈리지 않기

60

타임분석

O(n제곱)