[Python/기초] 조합과 순열

브루트포스문제에서 자주 사용되는 조합과 순열에 대해서 알아보자

itertools 모듈을 사용하면 매우 간단하게 구할수 있다.

---

조합 (combinations)

순서 상관 없이 n개 중 r개를 뽑는 경우

 

예시로 1,2,3 중에서 2개를 고를 때 가능한 조합

(1, 2)
(1, 3)
(2, 3)

(1,2)와 (2,1)은 같은 조합으로 취급한다.

사용 방법

from itertools import combinations

arr = [1, 2, 3]
for comb in combinations(arr, 2):
    print(comb)

시간 복잡도

• 경우의 수: nCr = n! / (r!(n - r)!)
• 입력 크기가 작을수록 사용 적합하다.

---

순열 (permutations)

순서 중요하게 n개 중 r개를 뽑는 경우

예: [1, 2, 3] 중 2개를 고르면:

(1, 2) (2, 1) (1, 3) (3, 1) (2, 3) (3, 2)

(1,2)와 (2,1)은 다른 순열이다.

사용법

from itertools import permutations

arr = [1, 2, 3]
for perm in permutations(arr, 2):
    print(perm)

시간 복잡도

• 경우의 수: nPr = n! / (n - r)!