(TIL) 20210614

📕Facts(한 것)

---

• 알고리즘 복습
• 프로그래머스 문제 풀기
• 수업듣기
• 자료구조, 알고리즘 포스팅(DP, radixsort, graph, MST)

📕Findings(배운 것)

---

기수정렬에서 LSD 정렬의 시간복잡도는 O(dN)이고

MSD 정렬의 경우 최선은 O(2N), 최악은 O(2dN)이다.

 

다익스트라는 그리디 알고리즘의 일종이지만 bellman-ford는 모든 경로를 탐색하는 알고리즘이다.

당연히 bellman-ford 알고리즘이 시간이 평균적으로 더 소요되고, 

다익스트라의 시간복잡도는 이진 힙 구조로 구현하는 경우O(E * logV), 배열로 구현하는 경우 V^2이며

bellman-ford의 경우 시간복잡도는 O(E*V)이다.

 

크루스칼 알고리즘의 시간복잡도는 O(E logE)이고 프림 알고리즘의 시간복잡도는 바이너리 힙으로 구현할 경우 O(E * logV)이다.

 

 

📕Feeling(느낀 점)

---

역시 머리에 넣으려면 여러번 자주 봐야햔다.

그리고 학교 수업만으로는 부족한 부분이 있기 떄문에, 교과서로 내용을 보충할 필요가 있다.

 

📕Affirmation(자기 선언)

---

• 日日新又日新
• 순간에 최선을

 

📕여담

---