알고리즘/알고리즘

[알고리즘] CheatSheet - python

다익스트라 import heapq def dijkstra(n): # O(ElogV) hq = [(0, n)] dis[n] = 0 while hq: cur_dis, cur_x = heapq.heappop(hq) if cur_dis > dis[cur_x]: continue for i, w in graph[cur_x]: new_dis = cur_dis + w if dis[i] > new_dis: dis[i] = new_dis heapq.heappush(hq, (new_dis, i)) 벨만 포드 def bellman_ford(n): # O(VE) min_d = [float('inf')] * (v + 1) min_d[n] = 0 for i in range(v): for j in range(e): a, b, w =..

[알고리즘] 소인수분해

n = int(input()) while n % 2 == 0: # 2로 나누어지면 n에 2를 나누고 2를 출력 n //= 2 print(2) for i in range(3, int(n ** .5) + 1, 2): # 3부터 루트n까지 2씩 증가 while n % i == 0: # i로 나누어지면 n에 i를 나누고 i를 출력 n //= i print(i) if n == 1: break # n == 1 이면 for문 탈출 if n != 1: print(n) # 입력받은 n이 소수이면 아무런 계산도 하지 않고 그대로 나옴 #입력값 72 #출력값 2 2 2 3 3 # 입력값 9991 # 출력값 97 103

[알고리즘] 특정 구간 소수 ( 에라토스테네스의 체 )

m, n = int(input()), int(input()) # 구간을 입력받는다 bool = [False, False] + [True]*(n-1) # 0과 1은 소수가 아니므로 False를 넣어둔다 for i in range(2, int(n**.5)+1): if bool[i]: for index in range(i*2, n+1, i): bool[index] = False # i의 배수에 False를 넣어준다 print([i for i in range(m, n+1) if bool[i]]) # m부터 n까지의 구간에서 bool[i]가 True인 값만 출력 # 입력값 3 20 # 출력값 [3, 5, 7, 11, 13, 17, 19]

[알고리즘] 소수 판정

p = int(input()) # p에 값을 입력받는다 bool = True if p 2 and p % 2 == 0: # p가 2보다 크고 짝수면 소수가 아니다. bool = False else: for i in range(3, int(p ** .5) + 1, 2): # 3부터 p의 제곱근까지 홀수만 나누어 본다 if p % i == 0: bool = False # p가 나누어떨어지면 소수가 아니다 break if bool: print('소수가 맞다') else: print('소수가 아니다') # 입력값 2 # 출력값 소수가 맞다