[알고리즘] - 경우의 수

곱의 법칙 Multiplication Principle

곱의 법칙은 두 개 이상의 독립적인 선택이 있을 경우, 전체 선택의 경우의 수를 계산하는 방법이다.

만약 첫 번째 선택의 경우의 수가 $n$가지이고 두 번째 선택의 경우의 수가 $m$가지라면 전체 경우의 수는 $n\times m$가지가 된다.

팩토리얼 Factorial

팩토리얼은 자연수 $n$에 대하여 $n$부터 $1$까지 모든 자연수의 곱을 의미한다.
$n$의 팩토리얼은 아래와 같이 계산이 된다.
$n! = n\times(n-1)\times(n-2)\times...\times 1$

순열 Permutation

순열은 서로 다른 $n$개의 물건 중 $r$개를 선택하여 순서 있게 배열하는 방법의 수를 의미한다.
순열의 수는 $P(n,r)$ 또는$_{n}\mathrm{P}_{r}$표기가 가능하다. 그리고 계산 방법으로는 아래와 같이 계산이 가능하다
$_{n}\mathrm{P}_{r} = \frac{n!}{(n-r)!} =n\times(n-1)\times(n-2)\times...\times (n-r+1)$

조합 Combination

조합은 서로 다른 $n$개의 물건 중에서 순서를 고려하지 않고 $r$개를 선택하는 방법의 수를 의미한다.
조합은 $C(n,r)$ 또는$_{n}\mathrm{C}_{r}$표기가 가능하다.
$_{n}\mathrm{C}_{r} = \frac{n!}{r!(n-r)!}$

조합의 계산 식은 순열의 셰간 식을 비교해서 도출이 가능하다.
$r$개의 대상을 정렬하는 방법은 $r!$가지 이므로, 나열하는 순서로 구현을 했을 경우의 패턴 수는 구별하지 않는 경우의 $r!$배가 된다. 결과적으로 $_{n}\mathrm{P}_{r}=r!_{n}\mathrm{C}_{r}$이 성립한다.

예제

$N$개의 카드를 갖고 있다. 왼쪽에서 $i$번째 카드의 색은 $A_i$이다.
$A_i=1$일 때는 붉은색 $A_i=2$일 때 노란색, $A_i=3$일 때 푸른색이다.
여기서 같은 색의 카드 2장을 선택하는 방법의 가짓수는?

여기서 문제 해결 방법으로 전체 탐색하는 방법이 있다. 해당 방법은 $N$개 중 2장의 카드를 선택하는 알고리즘으로 $O(N^2)$의 복잡고를 갖게 된다. 그렇기에 효율이 나쁘다.

붉은색, 노란색, 푸른색을 각각 $x, y, z$라고 할 때, 문제의 조건에 맞는 방법은

• 붉은색 카드 2장 선택 $_{x}\mathrm{C}_{2}$
• 노란색 카드 2장 선택 $_{y}\mathrm{C}_{2}$
• 푸른색 카드 2장 선택 $_{z}\mathrm{C}_{2}$

이렇게 각각의 색상에서 두장을 뽑는 경우의 수는 이렇게 될 것이다. 그래서 문제에서는 같은 색상의 카드 2장을 뽑는 경우의 수를 반환을 한다면 위 3가지의 경우의 수를 더해서 반환하면 된다.

$_{x}\mathrm{C}_{2}+_{y}\mathrm{C}_{2}+_{z}\mathrm{C}_{2} = \frac{x-(x-1)}{2}+\frac{y-(y-1)}{2}+\frac{z-(z-1)}{2}$
이렇게 각 색상의 경우의 수를 더하면 복잡도는 $O(N)$으로 해당 문제는 해결이 된다.

---

$N$개의 카드를 갖고 있다. 왼쪽에서 $i$번째 카드에는 정수 $A_i$가 표시되어 있다. 카드 5장을 선택하는 방법 중에서 선택한 카드에 표시된 숫자의 합이 딱 1000이 되는 경우의 수는?

처음 본 예제처럼 이 문제 또한 전체 탐색으로 해결이 가능 하겠지만 이번 문제는 5장의 카드를 선택하기 때문에 복잡도 또한 $O(N^5)$가 될 것이다.

하지만 이 문제는 $N$장의 카드에서 5장을 선택하는 방법은 $N^5$가 아닌 $_{N}\mathrm{C}_{5}$로 해야 한다.

$_{100}\mathrm{C}_{5} = \frac{100\times99\times98\times97\times96}{5\times4\times3\times2\times1} = 75287520$

75287520정도의 경우의 수가 계산된다. 이는 $10^9$의 수 보다 훨씬 작다.