[Python] 정리

21 Dec 2022 in Study on Algorithm

---

팁

# import sys
# sys.stdin.readline().split()
# input().rsplit() 뒤에서부터 / .strip() 줄바꿈 문자 제거 / .replace() 대체
# sys.stdout.write()
# input = sys.stdin.readline
# import math
# sorted_visit = sorted(visit, reverse=True)
# visit.sort(key = lambda item : item[1], reverse=True)
# sys.setrecursionlimit(10**6) #  파이썬은 재귀의 깊이를 제한 = 10**6, 그만큼 메모리 먹음
# from collections import deque -> 스택과 큐 대신
# import heapq -> 우선순위 큐(힙) 대신, heapify(리스트)

# input = sys.stdin.readline
# 최소공배수 (유클리드 호제법 이용)
# def lcm(a, b):
#     res = a*b
#     if b > a:
#         a, b = b, a
#
#     while b != 0:
#         a %= b
#         a, b = b, a
#     return res//a

# 리스트 복사
# list2 = list1[:]
# list2 = list(list1)
# list2 = list1.copy()
# list2 = [] + list1

# 그리디 알고리즘
# Fractional 배낭 = 선택한 최선의 값이 최적해를 구하는 방식과 같을때 귀류법(단위당 정렬)

# dp 알고리즘 = 처음 것이 무조건 아님
# 0/1 배낭 = 이전과 현재를 비교하며 최적해를 구함(2중 for)
# LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) = 연속되지 않는 같은 문자
# LCS(Longest Common Subsequence, 최장 공통 부분 수열) = 연속되지 않는 앞보다 큰 수

# 백트래킹 알고리즘
# 0/1 배낭 = 2**n만큼 실행하지만 가지치기
# 트리, 순회 등...

# BFS/DFS 알고리즘
# 그래프, 특정한 수만큼 변화 

# 최단경로 알고리즘
# 플로이드 워셜 = 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산(3중 for k i j)
# 다익스트라 = 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택(한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것 dist)
# 시간 줄이기 -> 우선순위 큐 활용

# 최소신장트리 알고리즘
# find = 원소가 속한 집합 찾기, Union = 두 원소 집합 합치기
# 집합 개념으로 집합에 속한 노드들을 트리라고 생각함.

# 위상정렬 알고리즘
# 우선순위가 있는 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬한 것입니다.

# INF = int(1e9)
# float("inf")

# 두 분리 집합을 하나로 합치는 것
# parent = [i for i in range(8)]
# def union(a, b):
#     a = find(a)
#     b = find(b)
#     if a < b:
#         parent[a] = b
#     else:
#         parent[b] = a

# 어떤 자식 노드의 최정상 부모 노드를 찾아 해당 원소가 속한 집합을 찾는 연산
# def find(x):
#     if parent[x] != x:
#         parent[x] = find(parent[x])
#     return parent[x]
# for i in range(n):
# 	find(i)

# 모듈러 연산
# 파이썬처럼 오버플로우가 발생하지 않는 언어를 쓰더라도 매우 큰 수를 곱하는건 시간이 오래 걸림.
# 그래서 FFT(고속 푸리에 변환)이라는 알고리즘을 사용해서
# 중간에 나머지를 구해 시간을 단축하고 오버플로우 발생 불가.
# (a+b)%p = ((a%p)+(b%p))%p
# (a*b)%p = ((a%p)*(b%p))%p
# (a-b)%p = ((a%p)-(b%p)+p)%p
# (a/b)%p = ((a%p)/(b%p))%p

# 페르마의 소정리(p = 소수, a와 p는 서로소이며 예시로 a = 2, p = 7)
# a^p = a (mod p)
# a^(p-1) = 1 (mod p)
# a^(p-2) = 1/a (mod p)