나그네

다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 시작 정점에서 모든 나머지 정점까지의 최단거리(cost)를 구하는 알고리즘 중 하나다. 주로 주어진 두 노드 사이의 최단거리(cost)를 구하는 데 유용하게 사용된다. 다익스트라 알고리즘 특징 정점의 개수가 V, 간선의 개수를 E일 때 O(ElogV)의 시간복잡도를 가진다. 모든 거리(cost)가 음수가 아닐 때만 사용할 수 있다. 우선순위 큐(최소 힙)를 사용한다. 다익스트라 알고리즘 작동 방식 아직 방문하지 않은 정점들 중 거리(cost)가 가장 작은 정점을 하나 선택해 방문한다. 해당 정점에 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 모든 정점을 방문하면 종료한다. 1번 과정을 위해 우선순위 큐(최소 힙)가..

유클리드 호제법(Euclidean Algorithm) 유클리드 호제법 두 개의 자연수의 최대공약수를 구하는 알고리즘 중 하나 2부터 1씩 늘려가며 두 자연수 중 작은 수까지 모두 나누어보는 방법은 시간복잡도가 O(N)인 반면 유클리드 호제법이란 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다. 최대공약수(Greatest Common Divisor, GCD) 공약수(Common Divisor)란 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 공약수 중 가장 큰 값을 의미한다. 최소공배수(Lowest Common Multiple, LCM) 공배수(Common Multiple)란 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수는 공배수 중 가장 작..