### 소인수 분해 ### : 합성수를 소수의 곱으로 나타내는 방법 (위키백과 https://mathbang.net/200) 인수 : 어떤수를 만들 때 곱해지는 각각의 것들(약수, a=b×c이면 b, c를 a의 인수) 소인수 : 인수(약수) 중에서 소수인 것들 #x는 줄여가면서 소인수는 늘려가면서 x를 소인수로 나눠 준다. def prime(x): p = 2 #소인수의 시작 factorization = [] #소인수를 저장하는 곳 # 시간 복잡도가 x ** 0.5일 때만 파악 # 소인수를 점점 늘려가면서 계산 while p ** 2 1: factorization.append(x) return fac
### 소수(Prime) ### : 1보다 크고 약수가 1과 자기자신인 수 1. 반복문 이용 def prime(x): #1을 제외하므로 2부터 시작 for i in range(2,x): #나눠지는지 파악 if x % i == 0: return False #시간 복잡도가 x**0.5이기 때문에 if i * i > x: break return True 2. ★에라토스테네스의 체★ : 어떤 수를 기준으로 해당 수의 배수를 다 지워가며 소수 찾기 def era_prime(x): a = [0 for _ in range(x+1)] #a: 소수인 경우 0나타낸다. p = [] #p: 소수값 저장 list for i in range(2, x): #소수인 경우 if a[i] == 0: p.app..
Dijkstra(다익스트라) - 하나의 노드에서 다른 모든 노드까지의 최단경로를 구하는 알고리즘 - 간선들의 가중치를 기억해서 해당 노드까지의 경로가 최소로 갱신하는 알고리즘 import heapq ex_visit = [0 for _ in range(n+1)] #전의 값을 저장하는 곳 visit = [[''] for _ in range(n+1)] #전체 경로 나타내는 곳 def djikstra(start): global ex_visit, visit wei = [1000000] * (n+1) #최단거리 heap = [] heapq.heappush(heap,(0, start)) #(거리, node) wei[s] = 0 while heap: weight, node = heapq.heappop(heap) for..
### 최대 공약수(GCD, Greatest Common Divider) ### : 0이 아닌 두 정수나 다항식의 공통되는 약수 중에서 가장 큰 수 ### 유클리드 호제법(Euclidean Algorithm) ### : a % b = R이라고 했을 때, a와 b의 최대공약수는 b와 R의 최대공약수와 같다 => GCD(a, b) = GCD(b, a%b) = GCD(b, a mod b) 1. #유클리드 호제법 사용 def GCD(a,b): if a % b == 0: return b return GCD(b, a%b) # 유클리드 호제법 반복문으로 변경 def GCD(a,b): while a % b != 0: a, b = b, a%b return b 2. 라이브러리(math) 사용 import math mat..
### Floyd-Warshall(플로이드-워셜) ### : 그래프에서 모든 정점간 사이의 최단 거리 찾기 => 모든 최단경로 구하기 == 모든 정점 최단 경로 알 수 있다. + 모든 경로를 돌아보는 것으로 왔다갔다한 것을 다 알 수 있다. 시간 복잡도: O(n^3) for i in range(n): for j in range(n): for k in range(n): if dist[j][k] > dist[j][i] + dist[i][k] dist[j][k] = dist[j][i] +dist[i][k]
하노이의 탑
### 하노이의 탑 ### : 3개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있다. : n개의 원판 일 경우 원판을 모두 마지막 기둥으로 옮길 수 있는 방법의 수는 (2^n) - 1번 이다 (메르센 수) 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있으면 안된다. # 첫 번째 규칙 1->2, 1->3, 2->3을 잘 생각해서 재귀 하면 된다. # 재귀할 때 해당 code 다 끝나면 돌아온다. def hanoi(n, from_, to_, by_): if n == 1: print(from_, by_) else: hanoi(n-1, from_, by_, to_) print(from_, by_) hanoi(n-1, to_, from_, by_)
DFS(깊이 우선 탐색) : stack, 재귀함수, check 사용 : 멀리 있는 노드를 우선으로 탐색하는 알고리즘 => 최단거리 + 가중치(이동과정 제약) 경우 사용 def dfs(graph,start_node): visited = list() #queue stack = list() #stack stack.append(start_node) while stack: node = stack.pop() if node not in visited: visited.append(node) stack.extend(graph[node]) return visited https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89