(2022-11-28) 코로나 격리 해제 D-1 일기

내일이면 코로나 격리에서 벗어날 수 있다. 흐흐

다음 주면 벌써 시험이라서 마냥 좋지만은 않네..ㅠ

밀린 진도 공부하고 시험 대비 공부에 팀프로젝트까지.. 너무 많다 

 

# 알고리즘 공부

오늘 공부는 prim Algorithm과 Bellmen-Ford 알고리즘, Dijkstra 알고리즘을 공부했다.

APSP(All-Pairs Shortest Paths)는 행렬을 이용하여 구하는데 행렬 곱 방식으로 계산 과정과 비슷하지만 곱하는 것이아닌 덧셈을 한 후 가장 작은 수를 선택하는 방법이다.

Slow-APSP는 O(n^4)만큼 걸리지만 Fast-APSP는 O(n^3lgn)만큼 걸린다.(약간 빨라졌네?)

 

플로이드 워셜 알고리즘

최단 경로를 구할 수 있는 알고리즘인데 D에 대한 행렬은 가중치를 표현했다가 직전 노드를 표시하는 ∏에 대한 행렬로 표현하는 알고리즘이다.

노드 수 만큼 알고리즘을 돌려서 표를 완성하며  ∏를 이용하여 최단 경로를 찾을 수 있다.

처음에 이해하는 게 힘들었는데 계속해서 읽다보니 완벽하게 이해했다! (이론은 완벽해!!)

 

이제 알고리즘 응용이랑 증명법 공부해야겟다..