파이썬
[Prime Number] 유클리드 호제법 (소수 찾기)
최대 공약수를 구하는 방법 중의 하나이다. 호제법은 두수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 개요 1071과 1029의 최대공약수를 구하면, 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21 42..
[Prime Number] 에라토스테네스의 체 (소수 찾기)
소수 판별법의 일종으로, 2부터 N까지의 자연수를 나열하고 2의 배수, 3의 배수, N//2 의 배수를 찾아가며 지워간다. 이후 남는 숫자가 2~N사이의 소수이다. APS에 심심치 않게 볼수 있는 소수를 찾는 방법 중하나이다. 중~하 문제에서 많이 나오기때문에 꼭 숙지하는 것이 좋다.소수는 약수가 1과 자기자신만 가지고 있는 숫자를 말한다. 소수를 찾는 방법은 직접 약수를 찾아가면서 소수인지 아닌지 확인하는 방법이 있다. 하지만 숫자에 범위에 따라 상황에 맞는 방법을 선택하면 실행속도가 더 빠르기 때문에 이 방법도 알아두는 것이 좋다. 개요 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기..
[Graph] Dijkstra algorithm (다익스트라 알고리즘)
다익스트라 알고리즘은 그래프 문제에서 최단 경로를 찾는 알고리즘이다. 정점 사이의 거리가 일정하지 않을 때 정점 A에서 정점 B로 가는 최단 거리를 찾는 방법이다. 정점사이의 최단거리를 갱신하며 더 짧은 것으로 저장하는 방식이다.자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다. 프림 알고리즘과 유사하게 초기 거리를 무한대로 설정하고, 새로운 경로가 기존값보다 짧으면 갱신한다. 구현 위 이미지와 동일한 정점과, 거리를 가진 그래프에 대해 1번 정..
[Graph] Kruskal’s algorithm (크루스칼 알고리즘)
크러스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 O(ElogV) 의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 크러스컬 알고리즘은 아래의 순서대로 작동한다. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F 을 만든다. 모든 변을 원소로 갖는 집합 S 를 만든다. S가 비어있지 않는 동안 가장 작은 가중치의 변을 S 에서 하나 빼낸다. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다. 그렇지 않다면 그 변은 버린다. 알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래..
[Graph] BFS (너비 우선 탐색)
너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다. 그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)로 크게 2가지가 있다. 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형식의 자료구조인 큐를 활용한다. BFS는 시작 정점 기준 거리가 가까운 곳부터 먼곳으로 탐색을 진행하기 때문에, 특정정점까지 가는 최단거리를 구하는데 용이하며, BFS 탐색이 종료된 경우 직전에 방문한 정점이 시점과 가장 먼 정점이라는 것을 알 수 있다. 개요 시작정점 v를 결정하여 방문한다. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있..