There and Back Again

크래프톤 정글 주제별 탐구 -크루스칼 알고리즘-

정의 크루스칼 알고리즘이란, MST를 구하기 위해 사용되는 알고리즘이다. 동작 방식 간단히 크루스칼 알고리즘의 동작 순서에 대해 작성해보자. 주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서(오름차순)로 정렬을 수행 정렬된 간선 정보를 하나씩 확인 하면서 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인 만약 사이클이 발생하지 ...

크래프톤 정글 주제별 탐구 -다익스트라 알고리즘-

정의 다익스트라 알고리즘은 DP(혹은 그리디)를 이용하여, 노드와 노드 사이의 최단 경로를 구하는 알고리즘이다. 동작 방식 간단한 다익스트라 알고리즘의 작동 방식에 대해 알아보자. 모든 노드의 이동 경로를 일단 나와있는 대로 2차원 배열을 통해 저장한다. 출발 노드를 설정한다. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. ...