Algorithm23 [Algorithm] 벨만 포드(Bellman-Ford) 알고리즘 벨만 포드 알고리즘(bellman-ford) 그래프에서 최단 거리를 구하는 알고리즘 기능: 특정 출발 노드에서 다른 모드 노드까지의 최단 경로 탐색 특징: 음수 가중치 에지가 있어도 수행할 수 있음 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 시간 복잡도: O(VE) (노드 수:V, 에지 수:E) 벨만 포드 알고리즘은 다음 3가지 단계의 원리로 동작한다. 1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 또한 최단 경로 리스틀 출발 노드는 0, 나머지 노드는 무한대로 초기화한다. edge 클래스는 일반적으로 노드 변수 2개(start,end)와 가중치 변수(w,v)로 구성되어 있다. 2. 모든.. 2023. 4. 15. [BOJ] 백준 1753 최단 경로 구하기 (python 파이썬) 백준 1753 최단 경로 구하기 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net Step 1 문제 분석하기 문제 모든 간선의 가중치가 10 이하의 자연수. 자연수는 양수이므로 모든 간선이 양수 -> 백준 1753은 전형적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 수행 과정 거리 리스트에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다. 즉, 우선순위 큐에서 데이터를 뽑아온다. .. 2023. 4. 13. [Algorithm] 다익스트라 (Dijkstra) 다익스트라 알고리즘 그래프에서 최단 거리를 구하는 알고리즘 기능 특징 시간 복잡도(노드 수:V,에지 수:E) 출발 노드와 모든 노드간의 최단 거리 탐색 에지는 모두 양수 O(ElogV) 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다. 다익스트라 알고리즘의 핵심 이론 다익스트라 알고리즘은 5개 단계로 나눌 수 있습니다. 1. 인접 리스트로 그래프 구현하기 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다. 2. 최단 거리 배열 초기화하기 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화합니다 이때 무한은 적당히 큰 값을 사용하면 됩니다. 코드로 실제 구현 시에는 MAX값으로 구현하면 됩.. 2023. 4. 11. [Algorithm] 그래프 위상 정렬(Topology Sort) 위상 정렬(topology sort) 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 기능: 노드 간의 순서를 결정 특징: 사이클이 없어야 함 시간 복잡도: O(V+E) (노드 수:V, 엣지 수:E) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다. 위상 정렬의 원리 1. 진입 차수 (in-degree): 자기 자신을 가리키는 에지의 개수 2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에서 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 참고자료 https://www.inflearn.com/course/lecture?co.. 2023. 4. 7. 이전 1 2 3 4 5 6 다음
