Search

조합과 순열이란?

생성일
2024/07/09

1. 조합과 순열의 수학적 개념

•
순열(Permutation)
◦
nn개의 원소 중에서 rr개의 원소들을 나열하는 경우의 수
◦
공식으로 나타내면 nPr_nP_r로 나타낸다.
▪
nPr=n⋅(n−1) ⋯ (n−r+1)_nP_r = n \cdot (n-1) \ \cdots \ (n-r+1)
◦
순열 시간 복잡도 상한치
▪
nPn_nP_n
•
조합(Combination)
◦
nn개의 원소 중에서 rr개의 원소들을 고르는 경우의 수
◦
공식으로 나타내면 nCr_nC_r로 나타낸다.
▪
nCr=nPrr!=n⋅(n−1) ⋯ (n−r+1)r!_nC_r = \frac{_nP_r}{r!} = \frac{n \cdot (n-1) \ \cdots \ (n-r+1)}{r!}
▪
nCr= nCn−r_nC_r = \ _nC_{n-r}
◦
조합 시간 복잡도 상한치
▪
nCn/2_nC_{n/2}

2. 조합 알고리즘과 순열 알고리즘

•
순열 알고리즘
◦
순열의 모든 경우를 살펴보는 알고리즘
순열 알고리즘 코드
◦
시간 복잡도: O(nPr)O(_nP_r)
•
조합 알고리즘
◦
조합의 모든 경우를 살펴보는 알고리즘
조합 알고리즘 코드
◦
시간 복잡도: O(nCr)O(_nC_r)

3. 조합과 순열의 관계

•
nCr_nC_r과 nPr_nP_r의 차이점에 대하여
•
nCr_nC_r은 nn개 중에서 rr개를 고르는 경우의 수이다.
•
nPr_nP_r은 nn개 중에서 rr개를 나열하는 경우의 수이다.
•
nPr_nP_r을 nn개 중에서 rr개를 고른 후에 나열한다고 생각해보자.
그러면, nCr_nC_r은 모든 경우에 대해 나열하면(순서를 바꾸면) 된다.
•
따라서, nPr= nCr ⋅ r!_nP_r = \ _nC_r \ \cdot \ r! 이며, 이 수식을 정리하면 다음과 같다.
◦
nCr=nPrr!_nC_r = \frac{_nP_r}{r!}