그래프3 다익스트라 (Dijkstra) 오늘은 최단거리 구하는 알고리즘 중 다익스트라 알고리즘에 대해 알아보려 합니다. 학교에서 갓 2학년에 되었을 때 알고리즘 수업시간에 다익스트라를 배웠었는데요, 사실 1학년 말에도 과 학회 선배들이 다익스트라를 알려줬었습니다. 하지만 저는 이것만큼 거부감드는게 없었어요ㅠㅠ 그냥 다익스트라 라는 단어 자체가 너무 어려워 보였던 것 같습니다. 하지만 이제와서 다시보니 왜 이렇게 간단한 개념을 이해조차 못했는지.. 이렇게 보니 저도 그 때보다 성장하긴 했나봐요ㅎㅎ.. 다익스트라는 V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점 (S) 에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (1:N) 입니다. 벨만-포드 알고리즘과 달리 음의 가중치를 가지지 않아, 각 정점을 최대 한.. 2021. 3. 9. 벨만-포드 (Bellman-Ford) 오늘은 최단 경로를 찾는 대표적인 기법 중 하나인 벨만-포드 알고리즘을 알아보려 합니다. 벨만-포드는 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점 S 에서부터 다른 정점까지의 최단경로 (1:N) 를 구하는 알고리즘입니다. 다익스트라와 달리 음의 가중치를 가진 간선을 가질 수 있고, 때문에 음의 사이클의 존재 여부를 확인해주어야 합니다. 최단거리를 구하기 위해 최대 (V-1)번 E개의 모든 간선을 확인하고, 음의 사이클을 확인하기 위해 한 번 더 E개의 간선을 확인합니다. 따라서 벨만-포드 알고리즘은 O(VE)의 시간복잡도를 가지게 됩니다. 구체적인 벨만-포드 Swift 코드를 보기 전에, 벨만-포드 알고리즘의 구현을 슈도 코드(Pseudo Code)로 먼저 보겠습니다. 슈도 코드.. 2021. 3. 8. 크루스칼 (Kruskal) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 보통 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하는 문제에서 적용됩니다. 크루스칼 알고리즘에서는 간선 리스트를 많이 이용합니다. 아래와 같이 방향이 있는 그래프에서는 출발, 도착 지점을 기록하고 비용이 있는 경우 추가적으로 기록해줍니다. 만약 방향이 없는 그래프라면 출발과 도착의 순서는 상관이 없습니다. 그럼 크루스칼을 한 번 구현해볼까요? 크루스칼을 구현하기 위한 단계를 간단하게 정리해보았습니다. Step 1. 비용이 적은 순서대로 간선 리스트를 정렬해줍니다. Step 2. 가장 위의 간선(비용이 가장 적.. 2021. 3. 4. 이전 1 다음
