벨만-포드 알고리즘 공부
벨만-포드 알고리즘 벨만-포드 알고리즘은 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘과 달리 음수 간선이 포함된 상황에서 최단 거리 문제를 해결할 수 있습니다. 전체 그래프에서 음수 사이클 존재...
Graph
플로이드-워셜 알고리즘 공부
플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 모든 노드에서 다른 모든 노드까지 최단 경로를 구하는 알고리즘입니다. 시간복잡도는 O(N^3)입니다. 이 글은 플로이드-워셜 알고리즘의 동작 과정과 코드 구현 방법에 대해서 정리한 내용입니다...
다익스트라 알고리즘 공부
다익스트라 알고리즘 다익스트라 알고리즘은 최단 거리를 구하는 알고리즘입니다. 시간복잡도는 O(ElogE)입니다. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다. 음의 간선이 없을 때 정상적으로 ...
크루스칼 알고리즘 공부
크루스칼 알고리즘 최소 신장 트리를 만들기 위한 알고리즘입니다. 시간복잡도는 O(ElogE)입니다. 이 글은 크루스칼 알고리즘의 동작 과정, 코드 구현 방법에 대해서 정리한 내용입니다.
그래프 표현 공부
그래프 표현 방법 그래프 알고리즘을 이해하기 위해서 그래프 표현 방법을 공부했습니다. 그래프를 표현하는 방법은 인접 행렬, 인접 리스트, 간선 리스트로 3가지가 있습니다. 이 글은 이 3가지 방법에 대해서 정리한 내용입니다.
유니온 파인드 공부
유니온 파인드 개념 여러 개의 노드의 노드가 존재할 때 두개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 그래프에서는 그래프의 사이클이 생성되었는지 판별하는 알고리즘으로 사용됩니다. 이 글은 유니온 파이드의 동작 원리와 그...