소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다. 어떤 자연수 n이 소수인지 판별하는 가장 기초적인 함수 코드는 아래와 같이 작성할 수 있습니다. def is_prime(n): for i in range(2, n): if n%i==0: return False ## 소수 아님 return True 2부터 n-1까지의 모든 수로 n을 나누어보는 방법입니다. 만약 나누어 떨어지는 수가 있다면 소수가 아닌게 되겠죠? 그럼 False를 리턴합니다. 그러나 이런 방법은 n까지의 모든 수를 확인해야 하기 때문에 시간복잡도는 ​O(n)​입니다. 따라서, n이 매우 크다면 비효율적이게 됩니다. ​ 좀 더 개선된 방법을 적용한 코드는 아래와 같이 작성할 수 있습니다. import math d..

- 크루스칼(Kruskal) 알고리즘이란? 크루스칼 알고리즘에 대해 설명하기 전, 서로소 집합 연산과 신장 트리에 대해 알아야 합니다! 그럼 각각에 대한 개념을 설명하겠습니다. ​ 1) 서로소 집합 서로소 집합이란! 수학적 의미 그대로 공통 원소가 없는 두 집합을 의미합니다. 두 개의 집합이 주어졌을 때 겹치는 요소들이 하나도 없어야 합니다. 두 집합이 서로소인지 판별하는 알고리즘은 다음과 같습니다. 1. 합집합 연산(union)을 통해 서로 연결된 두 노드 A와 B를 확인합니다. => A와 B의 루트 노드 A'과 B'을 각각 찾습니다. => A'를 B'의 부모 노드로 설정해줍니다. 2. 모든 합집합 연산을 처리할 때까지 1번 과정을 계속 반복해줍니다. 이 서로소 집합 연산을 이용한다면 무방향 그래프에서..

이번 포스팅에서는 플로이드-워셜, 벨만-포드 알고리즘에 대해 설명하겠습니다. - 플로이드 워셜 알고리즘(Floyd-Warshall) 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구하고 싶을 떄 사용하는 알고리즘입니다. 각 단계마다 해당 노드를 거쳐가는 경우를 고려해야 합니다. 예를 들어, 1번 노드에 있을때는 1번 노드를 거쳐가는 모든 경우를 고려하면 됩니다. A->1->B인 경우의 비용을 확인 후 최단 거리를 갱신해주어야 합니다. 이를 점화식으로 나타내면, 아래와 같습니다! min 함수를 사용해 바로 이동하는 거리와 특정한 노드를 거쳐서 이동하는 거리를 이용해 짧은 것으로 갱신될 수 있도록 해줍니다. 다익스트라 알고리즘은 매번 최단 거리를 검색하지만 이 알고리즘은 그럴 필요가 없다는 점이 장점..

최단 경로 알고리즘이란 단어 그대로 여러 개의 경로중에서 가장 짧은 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 "다익스트라 알고리즘"과 "플로이드 워셜"이 있습니다. 이번 포스팅에서는 다익스트라 알고리즘에 대해 설명하겠습니다. ​ ​ -다익스트라 알고리즘(Dijkstra) 여러 개의 노드가 있는 그래프가 주어지면, 특정한 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구할 수 있는 알고리즘입니다. 알고리즘의 동작과정은 아래 순서로 이루어집니다. 1) 먼저 출발 노드를 설정합니다. 2) 최단 거리 테이블을 초기화해줍니다. 3) 1에서 선택한 노드와 연결되어 있고 방분하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택합니다. 4) 3에서 선택된 노드를 거쳐 다음 노드로 가는 ..