다익스트라(Dijstra) 알고리즘은 그래프의 시작 노드에서 최종 목표 노드로 가기 위해 최단 경로를 구하는 알고리즘 이며, 최단 경로 탐색 알고리즘(Shortest Path) 이라고 부른다. 이 과정에서 오직 도착 노드 뿐만 아니라 다른 노드의 경로들을 방문하여 최단 경로를 찾아낸다. 이러한 목적을 달성하기 위해 매번 최단 경로의 노드를 탐색하기 된다. 동작 단계1. 출발 노드를 설정한다.2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.4. 해당 노드를 거쳐서 특정한 노드느로 가는 경우를 고려햐아 최소 비용을 갱신한다.5. 위 과정에서 3번 ~ 4번을 반복한다. 다익스트라는 일명 그리디 알고리즘 분류에 속하며, 최소 거리에 최..

먼 과거, ‘유클리드’ 라는 사람이 적은 책의 내용으로 2개의 자연수 또는 정식의 최대공약수를 구하는 가장 오래된 알고리즘으로도 알려저 있다. 먼저 호제법의 의미는 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘 방식을 뜻하며, 이 유클리드 호제법의 개념은 다음과 같다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라서, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 추가로, 최소공배수를 구하는 방법은 두 수 a, b를 곱한 수에 최대공약수를 나누어 나온..