[백준/11050/파이썬] 이항 계수 1

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

11050번: 이항 계수 1

Problem

자연수 N과 정수 K가 주어졌을 때, 이항 계수 (N,K)를 구하는 프로그램을 작성하세요.

조건

첫째 줄에 N과 K가 주어진다. 

(0<N<=10 , 0<=K<=N) 

SOL

Standard한 문제이다.

이항계수를 구현하는 방법은 많다.

 

이건 Input도 작으니, 그 어떤 방법으로든 구현이 가능하다.  만만한 것부터 시작하자.

 

Python3의 내장함수로 구현하기.

이항계수는 nCk로 나타내진다는건 잘 알려진 사실이다.(이항계수의 성질이라고 치면 엄 -청많이 나온다)

따라서, python에 내장되어있는 combination 함수를 쓰면 간단하게 구현이 가능해진다. combination은 모든 조합의 수를 iter로 반환해주므로, list로 변환해서 그 길이가 곧 경우의 수가 된다.

 

#자연수 N과 정수 K
from itertools import combinations

N,K = map(int,input().split())
combi = list(combinations(range(N),K))
print(len(combi))

 

이항계수의 정의

조합으로 나타낼 수 있다면, 당연히 factorial로 나타낼 수 있다. 조합은 factorial을 통해서 계산 하게 된다.

 

def factorial(n):
    ans=1
    for i in range(2,n+1):
        ans*=i
    return ans

def combination(n,k):
    return factorial(n)/ factorial(n-k)*factorial(k)

재귀적으로 구현

 

조합의 성질 중에서 아래와 같은 성질이 있다.

위의 수식은 다음을 의미한다.

N명 중 K명중 하나를 뽑는다는건,  1명을 기준으로 그 사람을 제외하고 나머지를 뽑는 경우의 수와 , 그 사람을 포함시켜서 나머지를 뽑는 경우의 합으로 나타낼 수 있다

 

예를들어 보자. 우리는 6명이서 3on3 농구를 하려고 합니다.

근데, 초록색 친구는 농구선수출신 입니다.  보통, 이런 상황에서 팀을 짜라고 한다면, 팀을 짜는 방법은 2가지가 있을겁니다.

 

• 초록색 친구는 팀 선택권 없이, 그냥 나머지 애들 중 그나마 잘하는 친구들 3명끼리 팀을 하고, 나머지를 초록색 팀으로 가게 해줄수 있습니다.
• 초록색 친구가 양심껏 2명을 뽑아서 , 팀을 구성할 수 있습니다. 

6명이서 팀을 구성하는데, 1명(Ace)을 기준으로 2가지 방법이 생겼습니다.

6C3 = 5C3 ( 5명 중, 그나마 잘하는 3명이 팀을 이루거나) + 5C2 ( 나머지 5명 중, 초록색이 양심껏 2명을 뽑음)

이 성립하게 됩니다. 아래와 같이 구현이 됩니다.

 

def combi(n,k):
	if k==0 or n==k:
    	return 1
    return combi(n-1,k) + combi(n-1,k-1)

combi(4,2)

 

재귀..?DP 못참지 ㅋㅋ

(대충 나루토 짤) 사실, 이거 보여줄려고 어그로 끌었다. 세계최강자들의 싸움이다

 

Bottom- up

이항계수가 재귀적으로 구현이 된다면, 우리는 DP의 가능성을 고려하지 않을 수가 없다. 천재 수학자님 파스칼님이 등장할 차례이다. 

13살 때, 파스칼님이 사용했던 방법이다.

저 파스칼 삼각형을 옆의 그림과 같이,  우리가 2차원 board로 구현한다면, 아래와 같은 식이 나오게 된다.

• DP[i][0] = 1
• DP[i][i] = 1
• DP[i][j] = DP[i-1][j] +DP[i-1][j-1] (단, 2<=j<K)

def combi(n,k):
	DP=[[0 for _ in range(K+1)] for _ in range(N+1)]
    
    for i in range(N+1):
    	DP[i][0] =1
    for j in range(K+1):
    	DP[j][j] = 1
    for i in range(1,N+1):
    	for j in range(1,K+1):
        	DP[i][j] = DP[i-1][j] + DP[i-1][j-1]
    return DP[n][k]

 

Top -down

 

Top -down 방식의 장점은 , 가독성(사람기준)이 좋다는게 장점이다. 이항계수 예제에서, 이 점이 여실히 드러나는데, 이항 계수의 Top-down 방식은 다른 DP들의 Top down 방식과는 조금 다른 의미를 가지게 된다. 이 변신을 잘 이해해보자.

 

즉, Top - down 방식 조금 더 의미론적으로 가까운 방식이다.

N개 중에서 매번 뽑을지/말지 정하고, 뽑은 갯수가 K가 되면 그만두는 (0을 반환하는)형식으로 구현을 한다.

이때, got==k 즉, true가 반환이 된다. * python에서는 true+true를 해보면, 2로 나타난다.

 

def bino_coef(n,k):
    if k> n :
        return 0
    DP =[[-1 for _ in range(n+1)] for _ in range(n+1)]
    
    def select(times,got):
        if times==n:
            return got ==k
        if DP[times][got] != -1:
            return DP[times][got]
        DP[times][got] = select(times+1,got) + select(times+1,got+1)
        return DP[times][got]
    
    return select(0,0)

이 생각의 아름다운 점은, k개 이상을 선택했을 때/k개 이하를 선택했을 때 등으로 생각의 확장이 가능하기 때문이다. 

즉, 각각의 시행을 독립적으로 분리 함으로써, 몇개를 선택하는지에 대해서도 자유로워 지고, 각각의 시행에서 확률을 부여해주면, 최종 확률을 계산하는데도 용이해진다.

def bino_coef(n,k):
    if k> n :
        return 0
    DP =[[-1 for _ in range(n+1)] for _ in range(n+1)]
    
    def select(times,got):
        if times==n:
            return got >=k
        if DP[times][got] != -1:
            return DP[times][got]
        DP[times][got] = (확률) *select(times+1,got) + (확률)*select(times+1,got+1)
        return DP[times][got]
    
    return select(0,0)

 

 

Refer

SUNGHWAN 님의 블로그입니다. 항상 많은 도움을 받고 있습니다.

 

조합 3가지 방법

[조합론] 이항계수 알고리즘 3가지