파이썬에서 단골로 등장하는 문제 유형 가운데 하나, ‘경우의 수’다.

순열(permutations) 관련 문제가 가장 자주 등장하는 것 같은데, 조합(combinations)이나 주사위 확률 같은 문제도 이따금 나온다. 매번 나올 때마다 헷갈린다. 이참에 정리해둔다.

(위키독스 페이지(https://wikidocs.net/23278)가 많은 도움이 됐다.)

파이썬에는 itertools 라이브러리가 있다. 그 안에 permutations(순열)와 combinations(조합) 함수가 있다. 이 라이브러리를 쓰면 문제 유형에 따라 순열과 조합을 손쉽게 구할 수 있다. 물론, 라이브러리 도움 없이 직접 계산할 수 있는 식도 함께 알아두자.

경우의 수에서 중요한 건 딱 두 가지, ‘순서’와 ‘중복’이다.

1. 순서 O, 중복 X

순열(permutations) 문제다.

예컨대, 1부터 5까지 숫자가 적힌 카드를 차례로 두 번 뽑는 경우다.

from itertools import permutations
p = list(permutations(range(1, 6), 2))
'''
[(1, 2),
 (1, 3),
 (1, 4),
 (1, 5),
 (2, 1),
 (2, 3),
 (2, 4),
 (2, 5),
 (3, 1),
 (3, 2),
 (3, 4),
 (3, 5),
 (4, 1),
 (4, 2),
 (4, 3),
 (4, 5),
 (5, 1),
 (5, 2),
 (5, 3),
 (5, 4)]
'''
print(len(p)) # 20

이 때 경우의 수를 구하는 공식은 다음과 같다.

$p={\frac{n!}{(n-k)!}}$

5개 카드에서 순서대로 2개를 뽑는다면,

$p={\frac{5!}{(5-2)!}}={5}×{4}={20}$ 이 된다.

2. 순서 O, 중복 O

주사위를 두 번 던져 나오는 경우의 수가 이 사례에 속한다.

itertools의 product 함수를 이용한다.

from itertools import product
p = list(product(range(1, 7), range(1, 7)))
print(len(p)) # 36

이때 경우의 수는 n²이다.

즉, 주사위를 두 번 던졌을 때 나올 수 있는 숫자의 경우의 수는 6² = 36이 된다.

3. 순서 X, 중복 X

조합(combinations) 문제다. 로또 번호 생성기가 대표 사례다.

여기선 1부터 4까지 숫자 가운데 2개를 조합하는 경우를 코드로 구현해 보자.

from itertools import combinations
c = list(combinations([1, 2, 3, 4], 2))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
print(len(c)) # 6

조합을 구하는 식을 팩토리얼을 이용해 구현하면 아래와 같다.

${c}={\frac{n!}{(n-k)!k!}}$

1-4 숫자에서 2개를 조합한다면,

${\frac{4!}{(4-2)!2!}}={4}×{3}÷{2}={6}$ 이 된다.

조합을 재귀함수로 구하는 방법은 아래와 같다. (참고 : https://deftkang.tistory.com/179)

def solution(arr): 
    n = len(arr) 
    picked = [] 
    start = 0 
    
    def recur(start, n): 
        # basecase(4개 선택)
        if len(picked) == 4: 
            print(picked) 
            return 
        # 1개선택 
        for i in range(start, n): 
            picked.append(i) 
            # 재귀하면서 나머지 원소 선택 
            start = picked[-1] + 1 
            recur(start, n) 
            picked.pop() 
    recur(start, n) 

solution([0,1,2,3,4])

4. 순서 X, 중복 O

1부터 4까지 적힌 카드 2쌍에서 하나씩 동시에 뽑을 때 이런 경우가 된다. 조합과 비슷하지만, 같은 숫자의 중복을 허용하는 점이 다르다.

itertools의 combinations_with_replacement 함수를 사용한다.

from itertools import combinations_with_replacement
c = list(combinations_with_replacement([1, 2, 3, 4], 2))
'''
[(1, 1),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 2),
 (2, 3),
 (2, 4),
 (3, 3),
 (3, 4),
 (4, 4)]
'''
print(len(c)) # 10

이 때 경우의 수는,

${c={\frac{(n+k-1)!}{(n-1)!k!}}}$ 이다.

위 경우 ${\frac{(4+2-1)!}{(4-1)!2!}}=5×2=10$ 이 된다.

좀, 복잡하지만 반복 학습을 통해 기억해두자.