패스트캠퍼스 챌린지 21일차(02/14) 데일리 미션 - 월요일

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

안녕하세요~! 21일차 챌린지입니다. 3주차 데일리미션 제출하는 날이기도 하죠. 근데 시간이 벌써... 1시간 가량밖에 안 남아서 쬐끔 조급합니다. 이상하게 일정이 밀리고 바뀌고 하다보니 월요일이 굉장히 바빠져버려서 지금밖에 시간이 안 나는군요.

오늘은 프림 알고리즘입니다. 크루스칼이랑 마찬가지로 MST 구하기에 이용되는 알고리즘이고, 크루스칼이랑 방식이 비슷한데 조금 달라요. 둘 다 그리디를 기반으로 해서 순간마다 최선의 선택을 하는건 동일한데, 이제 그 선택이 어떤 범위 안에서 이루어지냐가 다릅니다.

크루스칼은 전체를 다 보면서 비용이 제일 적은 엣지들을 선택해나갔다면 프림은 현재 정점에서 갈 수 있는 곳중에 비용이 최소인 곳을 골라서 움직이게 돼요. 하지만 두 방법 다 신기하게도 minimum cost가 보장됩니다.

당연히 코드상으로 구현하는 방식도 조금 다른데, 크루스칼은 유니온-파인드 연산을 썼다면 프림은 우선순위큐(priority queue)를 메인으로 사용합니다.

프림으로 구현할 때도 주의점은 비슷해요. 사이클이 생기면 안 되며 최종적으로는 모든 정점을 포함해야 합니다. 그리디인데도 최선의 경우가 보장된다는게 정말 신기해요! 

다 완성된 코드를 보니 오늘도 역시 걱정부터 앞섭니다. 저걸 내가.. 처음부터 끝까지 다시 혼자 스스로! 구현할 수 있을까?? 하는 그런거죠. 그리고 물론 이것도 안 해보면 모르겠죠?!

오늘의 챌린지도 여기서 마무리하도록 하겠습니다. 혹시나했지만 역시나... 프림도 내일까지 들어야 할 것 같아요. 한번에 다 듣긴 오늘 정말 시간이 안 따라주는 ㅠㅠ;

 

 

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

https://bit.ly/37BpXiC

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

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