• 이코테 영상 참고했숩니다

입력

2차원배열 입력

graph = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]    
arr = [[0 for i in range(m)] for i in range(n)]

n개의 string 입력

data = [sys.stdin.readline().strip() for i in range(n)]

소수 판별

import math

# 소수 판별 함수
def is_prime_number(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

에라토스테네스의 체

def prime_list(n):
    sieve = [True] * n

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True: 
            for j in range(i+i, n, i):
                sieve[j] = False

자료구조

Defaultdict

from collections import defaultdict
d = defaultdict(int) # int, list, set 다 가능

우선순위 큐 1 (heapq)

import heapq
que = []
heapq.heappush(que, i)
j = heapq.heappop(que)

• queue.PriorityQueue()는 thread safe한 대신 속도가 느리다. 코테에서는 heapq를 씁시다.

알고리즘

위상정렬

from collections import deque

v, e = map(int, input().split())
indegree = [0]*(v+1)
graph = [[] for i in range(v+1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result=[]
    q = deque()
    for i in range(1, v+1):
        if indegree[i]==0:
            q.append(i)
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] ==0:
                q.append(i)
    for i in result:
        print(i, end=' ')

topology_sort()

트리 순회

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
# 전위 순회
def pre_order(node):
    print(node.data, end='')
    if node.left_node != None:
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])
#중위 순회
def in_order(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end='')
    if node.right_node != None:
        in_order(tree[node.right_node])
#후위 순회
def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end='')

n = int(input())
tree = {}

for i in range(n):
    data, left_node, right_node= input().split()
    if left_node ==".":
        left_node = None
    if right_node == ".":
        right_node = None
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

세그먼트 트리

import sys
input = sys.stdin.readline

def init(node, start, end): 
    if start == end :
        tree[node] = l[start]
        return tree[node]
    else :
        tree[node] = init(node*2, start, (start+end)//2) + init(node*2+1, (start+end)//2+1, end)
        return tree[node]
 

def subSum(node, start, end, left, right) :
    
    if left > end or right < start :
        return 0
    if left <= start and end <= right :
        return tree[node]
    return subSum(node*2, start, (start+end)//2, left, right) + subSum(node*2 + 1, (start+end)//2+1, end, left, right)
 
def update(node, start, end, index, diff) :
    if index < start or index > end :
        return
    tree[node] += diff
    if start != end :
        update(node*2, start, (start+end)//2, index, diff)
        update(node*2+1, (start+end)//2+1, end, index, diff)
n, q = map(int, input().rstrip().split())
l = []
tree = [0] * ((4*n))
l = list(map(int, input().split()))

init(1, 0, n-1)

그다음부터는 알아서 ㄱ

벨만포드

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 다음 과정을 N-1번 반복
   1. 전체 간선 E개를 하나씩 확인
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

• 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 한 번 더 수행
• 이때 최단거리 테이블이 갱신된다면 음수 간선 순환이 존재

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 10억

def BellmanFord(start):
    # 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n번의 라운드를 반복
    for i in range(n):
        # 매 반복마다 "모든 간선"을 확인하며
        for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n-1:
                    return True
    return False


n, m = map(int, input().split()) # 노드, 간선의 개수
edges = [] # 모든 간선에 대한 정보를 담는 리스트
dist = [INF] * (n+1) # 최단거리 테이블을 모두 무한으로 초기화

# 모든 간선 정보 입력
for _ in range(m):
    a,b,c = map(int, input().split()) # a노드에서 b노드로 가는 비용이 c
    edges.append((a,b,c))

# 벨만포드 알고리즘 수행
negative_cycle = BellmanFord(1) # 1번 노드가 시작 노드

if negative_cycle:
    print("-1")
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
    for i in range(2, n+1):
        if dist[i]==INF:
            print("-1")
        else:
            print(dist[i])