새로 알게 된 개념들

에라토스테네스의 체

여러개의 소수를 판별해야 할 때에는 에라토스테네스의 체를 사용한다.

• 2부터 N까지의 소수를 구한다고 했을 때 2부터 N까지 반복문을 돌면서 아래 과정을 반복하되, 지워진 수는 패스한다.
• 지워지지 않은 수가 소수다.

최빈값 구하기

importstatisticsarr=list()
mode=statistics.mode(arr)

백트래킹

모든 경우의 수를 탐색해야 할 때에는 재귀호출을 사용한다. (dfs)

깊은복사

importcopycopy.deepcopy()

람다식을 활용한 알파벳 스트링 입력받기

board=list(map(lambdax: ord(x)-65, input().rstrip()))

ABCDE -> [0, 1, 2, 3, 4]

2차원 배열 한 줄로 입력받기

N, M=map(int, input().split())
graph= [list(map(int, list(input()))) for_inrange(N)]

List에서 Heap 객체 생성

l= [4,3,5]
q=heapq.heapify(l)

RecursionError

최대 재귀 깊이 강제로 늘리기

importsyssys.setrecursionlimit(100000)

SQL

집계함수(group by)를 이용한 조건비교 where대신 having 사용

My Library

Permutation (_nP_r)

visited= [False] *npicked= []
defperm():
globaln,riflen(picked) ==r:
print(picked)
returnforiinrange(len):
ifnotvisited[i]:
picked.append(arr[i]) # 변화visited[i] =Trueperm() # 재귀호출visited[i] =Falsepicked.pop() # 복원

Combination (_nC_r)

# 조합의 경우 visited가 필요없음picked= []
defcomb(left):
globaln,riflen(picked) ==r:
print(picked)
returnforiinrange(left, n): # left ~ n까지만 탐색picked.append(arr[i]) # 변화comb(i+1) # 재귀호출 (마지막에 넣었던 index가 left가 된다.)picked.pop() # 복원

Dijkstra

importheapqdefdijkstra(start):
distance= [1e9]*(N+1)
distance[start] =0h= [(0, start)]
whileh:
dist, now=heapq.heappop(h)
ifdist==distance[now]:
fortarget,dingraph[now]:
ifdist+d<distance[target]:
distance[target] =dist+dheapq.heappush(h, (dist+d, target))
returndistance

Union_Find

deffind(x):
ifx==parent[x]:
returnxparent[x] =find(parent[x])
returnparent[x]
defunion(x,y):
x=find(x)
y=find(y)
ifx!=y:
parent[y] =x

Eratosthenes' sieve

deferatosthenes_sieve(N):
prime= [True] * (N+1)
foriinrange(2, int(N**.5) +1):
ifprime[i]:
forjinrange(i+i, N+1, i):
prime[j] =Falsereturn [iforiinrange(2, N+1) ifprime[i]]

Topology Sort

fromcollectionsimportdequeconditions= [[]]
degree= []
result= []
q=deque()
foriinrange(N): ifdegree[i]==0: deque.append(q, i)
whileq:
a=deque.popleft(q)
result.append(a)
forbinconditions[a]:
degree[b] -=1ifdegree[b]==0: deque.append(q, b)

Segment Tree

arr= [] # source arraytree= [0]*(4*N)
# initialize the treedefinit(start, end, node):
ifstart==end: tree[node] =arr[start]
returntree[node]
mid= (start+end)//2tree[node] =init(start,mid,node*2) +init(mid+1,end,node*2+1)
returntree[node]
# sum of left~rightdeft_sum(start, end, node):
globalleft, rightifstart>rightorend<left: return0ifstart>=leftandend<=right: returntree[node]
mid= (start+end)//2returnt_sum(start,mid,node*2) +t_sum(mid+1,end,node*2+1)
# change valuedefupdate(start, end, node):
globalindex, diffifstart<=index<=end:
tree[node] +=diffifstart!=end:
mid= (start+end)//2update(start,mid,node*2)
update(mid+1,end,node*2+1)
# maininit(0, N-1, 1)
left, right=a, bprint(t_sum(0, N-1, 1))
index, diff=i, xupdate(0, N-1, 1)

index가 1부터 시작시 arr=[0]+[], init(1,N,1)

Binary Search

defbin_search(left, right):
globaltargetwhilel<=r:
mid= (left+right)//2iftarget<arr[mid]:
right=mid-1eliftarget>arr[mid]:
left=mid+1else: returnmidreturn-1

Upper Bound

defupper_bound(left, right):
globaltargetwhilel<=r:
mid= (left+right)//2iftarget<arr[mid]:
right=mid-1eliftarget>=arr[mid]:
left=mid+1returnright