이항계수(Binomial Coefficient)

 ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

이항 계수 - 위키백과, 우리 모두의 백과사전

 매일 매일 알고리즘 문제를 하나씩 풀고 있는데, 오늘 문제에서는 이항계수라는 개념이 나와서 정리해보려고 한다.

 본 내용은 위의 링크를 토대로 학습한 내용을 정리한 것이다.

---

이해하기

 우선 이항계수가 어떤건지 의미를 찾아보았다. 이항계수는 이항식을 이항정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

 이렇게 설명하면 되게 어렵게 느껴지니까 차근차근 정리해보자. 이항정리란 항이 두 개인 거듭제곱(예를 들어, (x+y)^2)을 풀어내는 것을 말한다. 예를 들었던 (x+y)^2를 이항정리해보자.

(x+y)^2

(x+y)(x+y)

x^2+xy+yx+y^2

x^2+2xy+y^2

 위 표는 이항정리를 해가는 과정을 나타낸 것이다. 두번째에서 세번째 과정을 유심히 살펴 보자. 이 때, 앞의 (x+y) 중에 하나(x나 y)를 고르고, 뒤의 (x+y) 중에 하나(x나 y)를 골라 그 둘을 곱하는 과정을 거쳤다. 만약 2제곱이 아니라 4제곱이라면 어떻게 될까? (x+y)(x+y)(x+y)(x+y) 이렇게 네 개의 칸에서 각각 2개 중 1개를 꺼내는 경우의 수와 같을 것이다.

 그렇다면 이제 이항계수를 알아보자. 이항계수는 거듭제곱 (1+x)^n을 이항정리했을 때, x^k의 계수를 말한다. 그렇다면 이항계수는 n개의 상자(x+y)에서 x를 k개 꺼내는 경우의 수이다.

---

코드로 나타내기

www.acmicpc.net/problem/11050

11050번: 이항 계수 1

 오늘 내가 푼 문제는 바로 이 문제다. 사실 이항계수를 몰라서 검색해서 찾아보니까 조합기호가 있길래 조합을 이용해서 풀어서 간단히 성공.

이 문제에서는 자연수 n과 정수 k가 주어졌을 때 이항계수를 구하라고 써있는데 풀이는 정말 간단하다.

from itertools import combinations
import sys

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

combi=combinations(range(n), k)

result=0
for c in combi:
    result+=1

print(result)

 파이썬에서는 itertools의 combinations를 이용해서 간단하게 조합을 구할 수 있다.

def combinations(iterable: Iterable[_T], r: int)
Return successive r-length combinations of elements in the iterable.

combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)

 참고로 만든 조합들의 개수를 구할 때 len()을 사용하면 아래처럼 에러가 난다. (len()을 사용할 수 없는 이유는 리스트처럼 단순한 배열이 아니기 때문인 것 같은데 좀 더 알아봐야 할 듯하다.)그렇기 때문에 for문을 돌리며 길이를 구했다.

예외가 발생했습니다. TypeError
object of type 'itertools.combinations' has no len()

 아래는 파이썬 공식 문서인데 itertools 모듈에 대한 자세한 정보를 원하면 참고하길 바란다.

docs.python.org/ko/3/library/itertools.html

itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.9.1 문서