알고리즘 Cheat Sheet

#패키지

from math import sqrt #제곱근
from math import gcd #최대공약수

from collections import Counter #딕셔너리 형태로 중복된 원소와 그의 개수 출력

from collections import product #AxB 데카르트의 곱(집합의 곱)
from collections import permutations #순열
from collections import combinations #조합
from collections import combinations_with_replacement #중복조합(H)

 

#함수

##최빈값 구하기
from collections import Counter
Counter(n_list).most_common(n) 
 #n_list에 있는 원소의 개수를 세고, 빈도 수로 정렬한 뒤 n개까지 출력


##순열의 개수 구하기
import math
#경우의 수를 구할때는 itertools 말고 math로 구하기
#math.comb(n, r) 조합.순서상관X  , math.perm(n, r) 순열.순서상관O
#n = n*n-n 으로 함수 없이 구하기 가능 nPr = n!/(n-r)! = n*(n-1)


#닫았다 열었다를 반복하는데 마지막이 열림이려면!->약수의 개수가 홀수개 여야함
##즉 제곱인 수들의 개수 == 열려있는 창문의 개수
print(int(int(input())**(0.5))) #입력된 숫자의 제곱근 == 제곱인 수들의 개수


##에라토스테네스의 체: 여러개의 숫자가 주어졌을때 소수 판별하기
n=10
a = [False,False] + [True]*(n-1)
primes=[] #소수만 출력하기 위해

for i in range(2,n+1): #2,3,4,5,6,7,8,9,10
  if a[i]: #true이면
    primes.append(i) #집어넣기
    for j in range(2*i, n+1, i): #2배수 한 것 부터 주어진 범위까지 i단위씩
        #i의 배수
        a[j] = False #false로 바꿔주기->false라서 for문 돌면서 true체크할때 조건 만족 안함
print(primes)


##소수인지 확인해주는 함수
def check(N):
    if N==0 or N==1: #예외 경우
        return False
    for n in range(2,int(sqrt(N))+1): #2부터 시작해서 약수가 있는지 확인
        if N%n == 0:
            return False
    return True #약수도 없고 예외도 아니면 소수 == True
    
    
#gcd(최대 공약수 구하는 함수 활용법)
gcd(a,b) #a,b의 최대공약수
gcd(*n_list) #리스트 안에 있는 모든 수들의 최대공약수


#gcd없이 최대 공약수 구하기
##최소공배수 = a*b//gcd(a,b)
'''
## 최대공약수 (유클리드 호제법)
#ex) 12와  64의 최대 공약수
#64 = 12*5+4
#12 = 4*3+0
#(64,12) == (12,4)
'''
while y:
    #print("x:",x, "y:",y)
    if x > y:
        x,y = y,x%y #y값에 나머지를 넣어야함
    else:
        y %= x #x == 최대공약수


##zip(두 리스트에서 한번에 각 하나씩 총 두개씩 출력할 수 있도록 묶어줌)
for i,j in zip(A_list, B_list)
[[x,y] for x,y in zip(numbers[::2],numbers[1::2])] #이중리스트롤 단일 리스트로 변환


##set(집합으로 만들어줌, 중복불가 순서 없음)
##대칭 차집합 == (A-B) 와 (B-A)의 합집합
set(A)^set(B)


##딕셔너리 활용하기
n_dic = {p:i for i,p in p_dic.items()} #for문으로 딕셔너리에 값 넣기
p_dic.update(n_dic) #두 딕셔너리 합치기


##print할때 출력 형태 지정하기
print(*A) #A리스트의 원소들을 리스트 형태없이 출력
print(a, end = ' ') ; print(a, sep = ' ') #공백 주면서 출력하도록 지정 아무거나 들어갈 수 있음


##lambda 활용하기
word_list = sorted(set(word_list), key=lambda x:(len(x),x)) #1.길이 2.알파벳 순서로 각각 비교해서 정렬

#길이가 M이상인 단어만
more_M = list(filter(lambda x:len(x)>=int(M),word))

#1.자주 나오는 단어 앞에 배치, 2.길이가 길수록 앞에 배치, 3.사전순으로 앞에 배치
answer = sorted(Counter(more_M).items(), key = lambda x:(-x[1],-len(x[0]),x[0]))

#key값만 출력하기
answer = list(map(lambda x:x[0],answer))

#진법 변환 함수
def zinbap(n, q):
    rev_base = ''
    while n > 0:
        n, mod = divmod(n, q)
        rev_base += str(mod)
    return rev_base[::-1]

 

#Aha Moment

1. 값을 저장해서 비교하면 시간 오래 걸림 T/F로 판단해서 확인하기

 

2. 값 입력 받기

a,*n_list = map(int, open(0).read().split()) #첫번째 값만 a에 지정하고 나머지는 리스트에 넣기

_,A,B = open(0) #분리 안된형태로 입력받고 ＞.split()을 통해서 분리하기

n,*L=([*map(int,i.split())]for i in open(0)) #입력받은 값을 한줄씩 for문으로 받고 .split()을 통해 분리시켜서 int로 변환

 

3. 두 지점 사이 거리에 물건을 몇개 놓을 수 있는지 확인할 때

거리//최대공약수-1  :이미 있는게 있으니까 한개는 빼주기

 

4. 분수 통분할 때 곱셈을 이용해서 통분하고, 분모 분자의 최대공약수를 구해서 약분해주기

 

5. 집합기호

| : 합집합   & : 교집합   ^ : 대칭차집합

 

6. 인덱싱

A[::2] #2개씩 건너뛰기, A[1::2] #첫번째부터 2개씩 건너뛰면서 출력

 

7. for문에 if문 추가

list = [n for n,s in dic.items() if s=='enter']

 

8. 숫자 정렬할때 꼭 int쓰기! 

 

9. (n,2n) 소수 개수 구할때 max값은 2n으로 할 것!

 소수 구할때는 sqrt써서 반만 보기!