[PYTHON]_코테에서도 쓰일_조합_계산_파스칼의 삼각형_시간복잡도(이항정리, 이항계수) 사용하기!!

1. itertools.combination 사용하기

https://knowallworld.tistory.com/146

[Python] 순열, 조합, 중복순열, 중복조합(itertools이용한 백트래킹)

==> 참고하기

EX) 50C3

 

print(len(list(itertools.combinations(np.arange(50) , 3))))

 

 

2. 파스칼의 삼각형

이항정리의 점화식

 

이항정리의 점화식 예시

파스칼의 삼각형:

import sys
N, M = list(map(int, sys.stdin.readline().rstrip().split(' ')))

# DP 활용한 파스칼삼각형 풀기
# nCk = (n-1)C(k-1) + (n-1)Ck
# 파스칼 삼각형 선언
pascal = [0]
for dp in range(2, N+2):
     pascal.append([0]*dp)
print(pascal)
# # pascal[i] = [1, ?, ?, ..., ?, 1]에서 i는 nCk에서 n, 리스트의 인덱스는 k를 의미

pascal[1] = [1, 1]
for dp in range(2, N):
    pascal[dp][0] = 1
    for idx in range(1, dp):
        pascal[dp][idx] = (pascal[dp-1][idx-1] + pascal[dp-1][idx]) % 10007
    pascal[dp][-1] = 1
print(pascal)

if M == 0 or M == N:
    print(1)
else:
    print((pascal[N-1][M-1] + pascal[N-1][M]) % 10007)
#%%

5C2 = 10

파스칼

 

파스칼 정리

 

3. 시간복잡도(O(n) ) 

 

result = 1
N = 5
K = 3
for i in range(K):
    result *= N
    N -= 1
print('result : {}'.format(result))
print('N : {}'.format(N))
divisor = 1
for i in range(2, K+1):
    divisor *= i
print('divisor : {}'.format(divisor))
print( (result // divisor) % 10007)

result : 60
N : 2
divisor : 6
10

 

==> % 10007 은 왜하는건가? ==> 그냥 해!