패스트캠퍼스 챌린지 38일차(03/03) 데일리 미션 - 목요일

패스트캠퍼스 챌린지 38일차(03/03) 데일리 미션

다익스트라 알고리즘! 입력은 간선과 정점으로 이루어진 그래프로 들어오고, 이때 그래프는 음수 가중치가 없는 그래프여야 한다.

아웃풋은 시작점에서 모든 점까지의 최단 거리! 시간 복잡도는 O(ElogV)라고 합니다.

필요한 정보로는 dist[i] = 시작점에서 i번 정점까지 가능한 최단 거리 정보를 저장할 배열이다.

 

어떤 메커니즘이냐면 첫 번째 스탭은 dist 배열 초기화. dist[시작점] = 0, 나머지는 무한대로 초기화한다.

두 번째 스탭은 그래프가 비었는지 확인하는 것. 빼먹기 쉬운데 이런 처리도 잘 해주기!

세 번째로는 D에서 가장 작은 d를 가지는 자료(v, d)를 뽑아내는 것.

네 번째는 dist[v] < d인지, 가치를 확인한다. 이미 최단 거리보다 크면 더 고려할 필요도 없이 필요없는 정보이므로!! 가치 없는 정보는 바로바로 폐기해야 한다.

다섯 번째 스탭으로는 v, d를 통해 D에 새로운 정보를 추가하는 것이다. d + c < dist[w]라면, 새로운 최단 거리 경로를 찾은 것이므로 dist[w] = d + c로 갱신한다.

 

갑자기 왜 공부 내용을 저렇게 쓰냐고요? 학교에서 듣는데 제 옆에 사람이 있었거든요. 친구가... 근데 평소처럼 일기 쓰긴 그래서 ㅋㅋㅋㅋㅋㅋ 공부한거 요약 정리 하는 척 적었습니다. 부끄럽잖아요. 그래서 평소와 스타일이 달랐답니다... 지금이 더 유익해보이지만요... 무튼 적은 것도 아까우니 지우진 않고 냅두겠습니다. 제대로 적지도 않아서 남에게는 도움이 안 될 것 같네요. 뭐어때 나혼자 복습하는건데~~~

밥 먹고 쓰려니 굉장히 잠이 오네요. 식곤증 못버텨 ㅜㅜ 어제 진짜 4시간인가 자고 대피곤 코스를 달렸더니 11시에 잠들어버렸어요. 전날도 4시 가까이 잔걸 생각하면 ㅋㅋㅋㅋ 급 모범생입니다. 저녁에 운동갔더니 어? 필라테스가 오늘따라 멤버가.. 오래 다닌 사람밖에 없더라고요 쌤이 신나서 풀코스를 달렸습니다. 진짜 풀코스였음. 죽는 줄 알았어요. 끝나고 나니까 영혼이 탈탈 털려서 ㅋㅋㅋ 원래는 하고 나면 특정 부위가 조져졌는데 어젠 정말 그냥 전체적으로 탈타랕랕랄 털렸습니다. 하하. 그래도 온 몸이 개운해요 필테 짱!

암튼 오늘 후기도 여기서 마무리하겠습니다. 학교 수업 들으러 가야하거든요. 열심히 살자 4학년아...!!

 

#패스트캠퍼스 #패캠챌린지 #직장인인강 #직장인자기계발 #패스트캠퍼스후기 #한번에끝내는코딩테스트369Java편초격차패키지Online

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.