알고리즘/탐색과 그래프2 패스트캠퍼스 캐시백 챌린지 07일 프림 알고리즘. 이번에도 중반부로 오게 된 이유, 알고리즘 과목 중간고사 범위 중 하나인 프림 알고리즘을 학습하기 위해서였다. 프림 알고리즘이란 무엇인가? 하니 특징을 나열하면 이러하다. *프림 알고리즘은 MST(최소신장트리)를 구현하는 한 방법으로 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다. (하지만 크루스칼에 더더욱 비슷해 보인다) *프림 알고리즘을 대략적으로 설명하자면 보통 이렇게 하더라. -각 정점들은인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 추가한다. -우선순위 큐를 이용하여 임의의 정점부터 인접한 정점을 거리를 기준으로 정렬한다. -최소 거리의 정점을 꺼내서 다시 인접한 정점을 넣고 정렬한다. -반복한다. -??? -profit! ...... 하지만, 저건 sudo.. 2022. 4. 24. 패스트캠퍼스 캐시백 챌린지 06일 이번 차시에서 알아보는 것은 크루스칼 알고리즘이었다. 크루스칼 알고리즘? -> 저번에 정리했던 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘으로서, 매커니즘은 다음과 같다. -> 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. (1) 주어진 그래프의 모든 간선에 대해서, 간선의 연결비용을 낮은 순으로 오름 차순 정렬한다. (2) 정렬된 간선 순서대로 선택하면서, 간선의 양 끝 정점을 Union 한다. 단, 이때 선택된 두 정점이 같은 집합에 속해있다면 사이클(cycle)이 있다고 판단하고 포함시키지 않는다. 이러한 매커니즘을 바탕으로 최종 선택된 간선을 연결한 것이 최소 비용 신장트리이다. ※ 크루스칼 알고리즘은 사실상 서로소 집합만 정확히 알고 있으면 매커니즘은 어렵지.. 2022. 4. 23. 이전 1 다음
