패스트캠퍼스후기39 패스트캠퍼스 캐시백 챌린지 08일 ch05. 자료구조(큐)에 대하여 작성중. https://bit.ly/3L3avNW 패스트캠퍼스 [직장인 실무교육] 프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공. fastcampus.co.kr 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다. 2022. 4. 25. 패스트캠퍼스 캐시백 챌린지 07일 프림 알고리즘. 이번에도 중반부로 오게 된 이유, 알고리즘 과목 중간고사 범위 중 하나인 프림 알고리즘을 학습하기 위해서였다. 프림 알고리즘이란 무엇인가? 하니 특징을 나열하면 이러하다. *프림 알고리즘은 MST(최소신장트리)를 구현하는 한 방법으로 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다. (하지만 크루스칼에 더더욱 비슷해 보인다) *프림 알고리즘을 대략적으로 설명하자면 보통 이렇게 하더라. -각 정점들은인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 추가한다. -우선순위 큐를 이용하여 임의의 정점부터 인접한 정점을 거리를 기준으로 정렬한다. -최소 거리의 정점을 꺼내서 다시 인접한 정점을 넣고 정렬한다. -반복한다. -??? -profit! ...... 하지만, 저건 sudo.. 2022. 4. 24. 패스트캠퍼스 캐시백 챌린지 06일 이번 차시에서 알아보는 것은 크루스칼 알고리즘이었다. 크루스칼 알고리즘? -> 저번에 정리했던 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘으로서, 매커니즘은 다음과 같다. -> 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. (1) 주어진 그래프의 모든 간선에 대해서, 간선의 연결비용을 낮은 순으로 오름 차순 정렬한다. (2) 정렬된 간선 순서대로 선택하면서, 간선의 양 끝 정점을 Union 한다. 단, 이때 선택된 두 정점이 같은 집합에 속해있다면 사이클(cycle)이 있다고 판단하고 포함시키지 않는다. 이러한 매커니즘을 바탕으로 최종 선택된 간선을 연결한 것이 최소 비용 신장트리이다. ※ 크루스칼 알고리즘은 사실상 서로소 집합만 정확히 알고 있으면 매커니즘은 어렵지.. 2022. 4. 23. 패스트캠퍼스 캐시백 챌린지 05일 최단 경로 알고리즘 이해... 보통 말하는 최단 경로 문제와 일치한다. 그래프 이론에서 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다. 보통은 주어진 가중 그래프에서 (V는 꼭짓점, E는 변, 가중치 함수 f : E → R)이 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다. 이런 문제는 단일-쌍 최단 경로 문제라고 부르며, 아래의 일반화된 문제들과는 차이가 있다. *단일-출발 최단 경로 문제 .. 2022. 4. 22. 이전 1 2 3 4 ··· 10 다음
