대충쓰는 TIL 0729

다익스트라, 플루이드 워셜

다익스트라

• 어느 한 시작 노드에서 다른 모든 노드와의 최단거리

1. 초기 비용으로 채우고
2. 방문하지 않은 가장 비용이 작은 노드 선택
3. 선택한 노드를 거쳐서 가는 경우의 비용 계산해서 비용이 원래 비용보다 작다면 갱신

2, 3 반복

종료조건 : 모든 노드 방문시

가장 비용이 적은 노드를 선택할 때 우선순위큐를 사용하면 시간 절약가능

플루이드 워셜

• 모든 노드에서 다른 모든 노드까지의 최단거리

1. 2차원 배열을 초기 비용으로 채운다.
2. 모든 노드를 하나씩 살피면서 해당 노드를 거쳐서 특정지점에서 특정지점까지 가는 거리 계산 후 원래 비용보다 작다면 갱신
   이때 특정지점에서 특정지점까지 가는 경우는 n-1P2 (순열이다. 걍 대충씀)

따라서 시간복잡도는 O(N^3)

GIT

clone은 원본 원격저장소 그대로 내가 commit하고 싶으면 collarborator 하거나 아니면 pull request

fork는 원격저장소도 내꺼 그냥 카피해오는 것

여기까지 알겠는데 clone만 하면 내 레포짓에 안뜨더라,,

github웹페이지에서 수정해서 collarborator임에도 불구하고..!

해결방법은 clone해서 내 로컬에 불러오고 commit push하면 내 레포짓에 뜬다.