이항계수를 구하는 알고리즘 기초1 - 파스칼의 삼각형

1. 파스칼의 삼각형

 

이항계수에 대한 성질 $$nCr = n-1Cr-1 + n-1Cr$$을 이용하여 이항계수 값들을 미리 테이블에 저장해놓는다

 

시간복잡도는 $O(n^2)$

 

n과 r이 10000이상이면 사용하기 힘들지만 충분히 작다면 사용하지 않을 이유가 없을 정도로 충분히 빠르다

 

 

2. 알고리즘

 

2-1) 행의 수 t를 입력받는다

 

2-2) 1부터 t+1까지 모든 행에 대해 0으로 초기화한 2차원 배열 생성

 

-------------------

 

만약 행의 수가 아니고 최대 1000Cr까지 구하고 싶다면??? 1001개의 행을 받아야한다는 점을 기억해야한다

 

-------------------

 

2-3) 각 행의 맨 처음과 맨 끝은 1로 만들고

 

2-4) 나머지는 $nCr = n-1Cr-1 + n-1Cr$을 이용하여 pascal[n][r] = pascal[n-1][r-1]+pascal[n-1][r]로 저장

 

 

3. 코드 예시

 

3-1) 첫번째

t = int(input())

pascal = [[0]*i for i in range(1,t+1)]

for row in pascal:
    
    row[0] = 1
    row[-1] = 1

for n in range(2,t):
    
    for r in range(1,n):
        
        pascal[n][r] = pascal[n-1][r-1] + pascal[n-1][r]

 

3-2) 두번째

t = int(input())

pascal = [[0]*i for i in range(1,t+1)]

for n in range(t):
    
    for r in range(n+1):
        
        if r == 0:
            
            pascal[n][r] = 1
        
        elif r == n:
            
            pascal[n][r] = 1
        
        else:
            
            pascal[n][r] = pascal[n-1][r-1] + pascal[n-1][r]

print(pascal)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

 

4. 예시 문제

 

 

4-1) 크기가 N인 파스칼의 삼각형 출력

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5P0-h6Ak4DFAUq 

SW Expert Academy

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    pascal = [[0]*i for i in range(1,n+1)]
    
    for x in range(n):
        
        for r in range(x+1):
            
            if r == 0:
                pascal[x][r] = 1
            
            elif r == x:
                
                pascal[x][r] = 1
            
            else:
                
                pascal[x][r] = pascal[x-1][r-1]+pascal[x-1][r]
    
    print('#'+str(t))
    for row in pascal:
        print(*row)
    # ///////////////////////////////////////////////////////////////////////////////////

 

 

4-2) 이항계수를 특정 수로 나눈 나머지 구하기

 

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

최댓값 N이 1000까지이기때문에 미리 1000Cr을 구할 수 있도록 1001개의 행을 준비해놔야한다.

 

의식적으로 1000개의 행만 준비할 수도 있는데 그러면 999Cr까지밖에 못구한다

 

생각을 좀 하자

 

from sys import stdin

n,k = map(int,stdin.readline().split())

pascal = [[0]*i for i in range(1,1002)]

for x in range(1001):
    
    for r in range(x+1):
        
        if r == 0:
            pascal[x][r] = 1
        
        elif r == x:
            pascal[x][x] = 1
        
        else:
            pascal[x][r] = pascal[x-1][r-1] + pascal[x-1][r]
    

print(pascal[n][k] % 10007)

 

 

 

 

참조

 

https://rebro.kr/107

PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법