코테 알고리즘

다익스트라(최단거리)

import heapq
import sys
input = sys.stdin.readline()
INF = int(1e9)

graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    
def dijkstra(start):
    q= []
    heapq.heappush(q,(0,start))
    distance[start]=0
    while q:
        dist,now = heapq.heappop(q)
        if distance[now]<dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost<distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))

서로소 집합 알고리즘

def find_parent(parent,x):
    if parent[x]!= x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e = map(int,input().split())
parent = [0] * (v+1)

for i in range(1,v+1):
    parent[i]=i

for i in range(e):
    a,b = map(int,input().split())
    union_parent(parent,a,b)

신장트리

def find_parent(parent,x):
    if parent[x]!= x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

v,e = map(int,input().split())
parent = [0] * (v+1)

for i in range(1,v+1):
    parent[i]=i
edges = []
result = 0
for i in range(e):
    a,b,cost = map(int,input().split())
    edges.append((cost,a,b)) #비용순으로 정렬

edges.sort()

for edge in edges:
    cost,a,b =edge
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost

위상정렬

import sys
from collections import  deque
n,m = map(int,sys.stdin.readline().rstrip().split())

indegree = [0]*(n+1)

graph = [[] for i in range(n+1)]

for _ in range(m):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a] .append(b)
    indegree[b]+=1
print(graph)
def topology():
    q = deque()
    result = []
    for i in range(1,n+1):
        if indegree[i]==0:
            q.append(i)
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            print(i)
            indegree[i]-=1
            if indegree[i]==0:
                q.append(i)
    print(result)

topology()

2차원 배열 90도 회전하기

def rotate_matrix(a):
    row_length = len(a)
    column_length = len(a[0])

    res = [[0] * row_length for _ in range(column_length)]
    for r in range(row_length):
        for c in range(column_length):
            res[c][row_length-1-r]=a[r][c]

    return res

소수 판별 함수

def is_prime(x):
    for i in range(2,x):
        if x%i ==0:
            return False
    return True

bisect

from bisect import bisect_left, bisect_right

def count_ny_range(a,left_value,right_value):
    right_index = bisect_right(a,right_value)
    left_index = bisect_left(a,left_value)
    return right_index - left_index


a = [1,2,3,4,5]
x = 4

에라토스테네스의 체

소수를 찾는 방법

a = [False,False]+[True]*(20)


for i in range(2,20):
    if a[i]:
        for j in range(i*2,20,i):
            a[j] = False

print(a)

10진수를 n진수로 변환

def convert(n, base):
    T = "0123456789ABCDEF"
    q, r = divmod(n, base)
    if q == 0:
        return T[r]
    else:
        return convert(q, base) + T[r]

소수찾기

def is_Prime(n):
    temp = int(math.sqrt(n))+1
    for i in range(2,temp):
        if n%i==0:
            return False
    return True