코딩테스트/Python template
행렬의 곱셈
# 두 행렬 A,B를 곱해서 결과를 return한다 # input format은 [[1,2,3]],[[1],[2],[3]] 와 같이 곱할 두 행렬을 넣어주면 된다. # 만약 곱셈이 불가능한 경우 assertion에 걸린다. def multiple_matrix(A,B): # find dimension (row -> m, column -> n) m_A = len(A) n_A = len(A[0]) m_B = len(B) n_B = len(B[0]) assert(n_A == m_B) # return matrix return_matrix = [[] for _ in range(m_A)] tmp = list(zip(*B)) for i in range(m_A): for j in range(n_B): return_mat..
N*N 행렬의 제곱
# N*N행렬의 제곱을 구하는 함수 # matrix 에는 [[1,0],[0,1]] 과 같이 행렬이 N*N의 format으로 들어오면 된다. # return 또한 input format 과 같이 return된다 def square(matrix): N = len(matrix) return_matrix = [[] for _ in range(N)] tmp = list(zip(*matrix)) for i in range(N): for j in range(N): return_matrix[i].append(sum(map(lambda x : x[0] * x[1],zip(matrix[i], tmp[j])))) return return_matrix ''' # testcase print(square([[1,2,3],[1,2..
DP factorial
''' 0~n번째 factorial dp array를 return ex) dp_factorrial(5) : [1, 1, 2, 6, 24, 120] ''' def dp_factorial(n): dp = [0]*(n+1) dp[0] = 1 for i in range(1,n+1): dp[i] = dp[i-1] * i return dp
거듭제곱 분할정복
# 11^12를 구해야하면 # exp(11,12)를 하면 됨 # 실제 사용시 recursion함수이기에 recursion error와 # 나머지를 return 하라는 문제조건 등에 유의하기 # ps: 나머지를 return 해야할시 return이 붙은 모든곳에서 나누어주어야함!! def exp(base: int, expo: int) -> int: if expo == 0: return 1 if expo == 1: return base a = exp(base, expo//2) b = expo%2 # print(f'a,b = {a,b}') return a*a*(base**b) print(exp(2,0))