패스트캠퍼스 챌린지 20일차(02/13) 데일리 미션

패스트캠퍼스 챌린지 20일차(02/13) 데일리 미션

예~ 경축 20일차! 20일차입니다. 어느 새 3주가 지나갔네요. 감격스럽습니다. 그동안 기본이 되는 스킬들은 거의 다 배운 것 같아요. 진도율도 40퍼센트가 넘었구요. 다음 파트로 슝슝 넘어가고 싶지만 머리가 그렇게까지 따라주지는 않습니다. 

오늘은 예고한대로 크루스칼을 마저 했습니다. (사실 아직 조금 남음)

크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)의 가장 대표적인 알고리즘이고 그리디 알고리즘을 기초로 합니다. 왜냐하면 매 단계마다 현재 상태에서의 최소 비용을 선택하는 방식으로 구현되기 때문입니다.

우선 정점이랑 간선을 부분적으로 봅니다. 부분 컴포넌트를 만들어가면서 하나로 잇는다고 해야하나? 이산수학에선 이런 느낌으로 배웠습니다. 이산수학 열심히 했는데 2년전이라,, 헐 이제 3년전이네요. 3년전이라 정확하게 기억이 안 나네요. 필기를 다시 참고해야겠습니다.

그래서 좀 더 자세히 설명하자면, 눈으로 보고 푼다고 생각했을 때는 음.. 그래프 전체를 보고 제일 비용이 적은 길을 고르고, 그 다음 단계에서 또 고르고, 그 다음 또 고르고.... 하다가 정점이 전부 포함된 길이 나오면 그만둡니다. 이때, 길을 고르긴 고르는데 사이클이 만들어지면 안되므로 선택된 정점을 포함하는 안 선택된 간선들은 다 제외합니다. 패스여야하니까요!

그렇게 완성된 경로가 최단 경로인지는 이산수학에서 증명했었습니다. 어려운 말들이라 참 머리가 아팠었죠,,,

이걸 이제 코드적으로 보면, 말로는 쉬웠던 부분(전체를 보고 제일 적은 길을 고른다, 사이클이면 안 된다)들이 까다로워집니다. 그래서 특별히 Union-Find라는 두 개의 간단한 알고리즘을 사용해요. 유니온은 두 개의 다른 집합을 하나의 트리로 합치는 것, 파인드는 서로 같은 그래프에 속한 정점인지 판단하는 것입니다.

자세한 구현은 깔끔하게 정리가 되면 그때 정리글로 올릴거예요! 오늘은 공부 후기 겸 복습만!! 그럼 알고리즘 스터디를 위해서 가보겠습니다. 10시라서 빠듯하네요,, ㅜㅜㅜ월요일 싫어~~~

 

 

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

https://bit.ly/37BpXiC

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

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