[알고리즘,개념,조합] 이항계수, 조합의 수

https://dailymapins.tistory.com/246

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

제 글 이항계수 1번 글에 있는 개념을 정리한 글입니다 :)

 

이항계수(Binomial coefficient)

원래의 정의는 , (X+Y)^n과 같이 어떤 합의 꼴의 거듭제곱 식에서 계수가 어떻게 나오는지에 대해서 , 정리한 일종의 규칙이다. 예를들어, (x+y)^2 = x^2+2xy+y^2 에서, 계수는 1,2,1이다. 이걸 행렬로 나타낸 뒤, 조합을 이용하여 증명해놓은게 이항정리이다.  더 자세하게 들어가면 수학과가 되버리니, 여기까지만 알고있자.

 

이항계수는 파스칼 삼각형, 조합의 수 , 행렬 등 다양한 수학적인 방법을 이용해서 나타낼 수 있다.

하지만, 우리는 "알고리즘"으로써, 접근해야하고 이항계수를 관련된 문제는 주로 "조합"을 이용해서 많이 접근하게 된다.

즉, n개 중에서 K개를 뽑는 조합의 수를 직접적으로 내기에는 심심하니까, 이항계수를 많이 이용하게 된것 같은데, 우리는 결론적으로 "조합"에 대해서 공부하게 되는점을 명심하자! 

3줄 요약

• 이항계수 == 조합의 수
• 완전탐색 문제에서 조합은 밥먹듯이 나온다.
• 조합을 구현하는 여러가지 방법을 알고있자

 

조합을 구현하는 방법

Sol 1. 각 프로그래밍 언어의 내장함수로 구현하기

이항계수는 nCk로 나타낼 수 있다. 요즘은 각 언어마다 Combinations,permuntation과 같은 기본적인 조합,순열에 대한 함수는 다 가지고 있다. 따라서, 구현하는데 시간이 없거나, 급하게 써야하는 경우라면 , Python3의 Combination을 이용해보자.

* Python3의 Combinations는 모든 조합의 수를 이터럴 형식으로 반환하므로, list로 변환하면, List의 길이가 모든 경우의 수가 된다. 

from itertools import combinations

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

 

Sol2. Factorial로 직접 구현해보기

조합은 factorial로 나타낼 수 있고, 아래와 같은 식으로 계산이 되어진다.

nCr을 factorial으로 나타내기

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

combi(4,2)

Sol3. 재귀적으로, Combination 구현해보기.

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

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

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

정의를 들어도, 이게 무슨 소리인가 싶을거다. 나도 처음에는 그랬다 ㅠㅠ . 이해가 안될 때는, 예시를 들어서 흡수하는 게 제일 빠르다.  예를들어 보자. 우리는 6명이서 3on3 농구를 한다고 가정하고, 팀을 나눈다고 생각해보자.

그런데,  초록색 친구는 농구선수 출신이다. 그렇다면 , 이런 상황에서 팀을 짜라고 한다면, 팀을 짜는 방법은 2가지를 떠올릴 수 있다.

• 초록색 친구를 제외하고,  나머지 애들 중 그나마 잘하는 친구들 3명끼리 팀을 하고, 나머지를 초록색 팀으로 보낸다.
• 초록색 친구가 "양심껏" 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)

 

Sol4. 재귀 ? 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]

Sol5. 조합을 다르게 생각해보기. 생각의 전환

 

TOP - down

 

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

 

Top - down 방식이 보통, 조금 더 본질적인 의미에 가까운 방식일 때가 많다.

n개 중에서 k개를 뽑는다는 것은, n번의 기회가 있을 때, k개를 뽑으면 된다는 말이고, 한번의 기회에는 뽑느냐/안뽑느냐 2가지의 선택지 밖에 없다. 따라서, 아래와 같은 점화식이 성립이 된다. 

Func(times,got) = Func(times+1,got+1) + Func(times+1,got)

• got : 내가 times번째 기회일 때, 갖고있는 갯수 . times==n 일때, got ==k 이면 만족하는 경우이므로, return got==k을 해준다. 
• times: 몇번째 기회인지 나타내는 수이다.
• DP[times][got]은 메모이제이션을 위해서 만든 공간.

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)

 

이 생각이 왜  가치가 있을까?

• "n개 중에서 k개를 뽑는다"는 하나의 개념을 n번의 기회로 독립시킬 수 있다는 이야기이다.  이렇게 된다면, 각각의 뽑는 기회를 "독립"적으로 바라볼 수 있기 때문에, k에 대한 조건이 걸렸을 때, 수월하게 구현할 수 있게 된다.
• 예를들어, 100개 중에서, 60개 이상을 뽑는 경우의 수를 구한다면, 100C60 +100C61....와같이 구현해야하지만, 위에서는 return got==k 부분을 got >=k 와같은 형식으로 바꾸면 된다.
• 또한, 확률에 대한 계산도 가능해진다. 각각의 시행에서 확률을 부여해주면, 최종 확률을 계산하는데도 용이해진다.

Refer

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