240424 수학공부

약수,배수,소수

약수,배수

GCD 최대공약수 Greatest Common Divisor
LCM 최소공배수 Least Common Multiple ->LCM은 n*m/GCD

유클리드 호제법
def GCD(n,m):
while m:
n,m=m,n%m
return n

def LCM(n,m):
return int(n*m/GCD(n,m))

소수

에라토스테네스의 체(소수) -> 체로 치듯 걸러낸다

스택 큐 덱

스택

괄호문제는 스택을 이용하는 대표적인 문제

큐

deque배움
.rotate배움 회전시 -로 돌려야 방향맞음

덱

익셉션으로 -1처리하는거 좋음

이항정리&이항분포

nCr=n!/(r!*(n-r!))

기본성질1 nCr = nCn-r

기본성질2 가로줄 전부 더하면 2^n승 (0부터)

중복허용 이항정리 nHr -> n+r-1Cr

파스칼삼각형

n-1Cr-1 + n-1Cr = nCr 역삼각형모양으로 이루어진 숫자 간의 관계

하키스틱의 원리
nC0 + n+1C1 + n+2C2 + ... + n+rCr = n+r+1Cr
3C0 + 4C1 + 5C2 + 6C3 = 7C3
4C4 + 5C4 + 6C4 + 7C4 = 8C5

5C4는
5
( )
4 로 표현가능

240425 정렬

버블정렬 Bubble Sort
선택정렬 Selection Sort
삽입정렬 Insertion Sort
병합정렬 Merge Sort
퀵정렬 Quick Sort
힙정렬 Heap Sort 이건 아직 못해봄