최단 경로 문제란? 벨만포드 알고리즘을 다룬 여기 문서 참고 다익스트라 알고리즘 - 하나의 시작점에서 도착점으로 가는 최단 경로를 찾는 알고리즘 - 간선이 음의 값을 가져선 안 된다 1. graph, weight, start 가 주어진다 2. start(자기 자신)까지의 거리는 0으로 상정한다 3. 모든 vertex 들을 queue에 넣고 반복한다 - queue에 들어간 v 중에서 가장 작은 값을 찾아 뽑는다 - 뽑힌 v에 대해서 relaxation 수행 예제 현재 Q에서 가장 작은 값을 찾는다 --> $s$ $s$의 인접 노드 중에서 더 작은 $y$ 선택 $y$에서 relaxation 시행, 가장 작은 $z$ 선택 $z$에서 relaxation 시행, Q에서 가장 작은 $t$로 다시 돌아감 $t$에서 ..

최단 경로 문제란? - 정점 $u$에서 정점 $v$까지의 경로 중에서 경로의 값이 가장 작은 경로를 찾는다 - $\delta (u, v)$ 벨만포드 알고리즘 음수 간선의 값(negative-weight edges) 이렇게 생긴 경로 그래프가 있고, $s$ 에서 $g$로 가는 경로를 구하려고 한다. 총 세 가지 경로를 생각해볼 수 있는데, (1) $ab$ 를 거쳐가는 경로 (2) $cd$ 를 거쳐 가는 경로 (3) $ef$ 를 거쳐 가는 경로다. (1) $ab$ 를 거쳐가는 경로 길이 하나 뿐이므로 경로의 값을 모두 더해서 구하면 된다 -> $3$ (2) $cd$ 를 거쳐 가는 경로 $c$ 와 $d$ 사이가 싸이클 형식으로 되어 있으므로 $cd$ 안에서 싸이클을 돌고 이동할 수 있다 단 이 경로의 경우 싸..

빅오표기법과 시간복잡도 정의 - 인수가 특정 값이나 무한으로 향할 때 함수의 극한 행위(limiting behavior)를 표현해주는 수학적 표기 -> 데이터가 늘어날 때 알고리즘 성능이 어떻게 바뀌는가? - 알고리즘의 효율성을 상한선 기준으로 표기해준다 -> "최악의 시나리오" 복잡도 시간복잡도와 공간복잡도 - 시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수 ("데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가") - 공간복잡도 : 알고리즘이 실행될때 사용하는 메모리의 양 수학적 정의 $n \geq n_{0}$ 인 모든 $n$ 에 대해 $f(n) \leq cg(n)$ 인 양수 $c,\ n_{0}$ 가 존재한다면, $f(n)$ 을 $O(g(n))$ 이라고 나타낼 수 있다 $n$은 $O(n..