### 소수(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..
### 덱(deque) ### :양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조 (stack + queue) from collections import deque #deque 만들기(stack,queue를 합쳐 놓은 것) de = deque() #왼쪽에 값 추가 de.appendleft() #오른쪽에 값 추가 de.append() #왼쪽에 값 확장 de.extendleft() #오른쪽에 값 확장 de.extend() #값 삭제 de.remove() #맨 왼쪽값 출력 후 제거 de.popleft() #맨 오른쪽값 출력 후 제거 de.pop() #값 회전(오른쪽) de.rotate(1) #값 회전(왼쪽) de.rotate(-1)
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]