Skip to main content
동호의 블로그

조합과 순열이란?

•1 min•184 words

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. 조합 알고리즘과 순열 알고리즘

  • 순열 알고리즘
    • 순열의 모든 경우를 살펴보는 알고리즘
순열 알고리즘 코드 
N = 4
R = 3
lst = [1, 2, 3, 4]
check = [False] * N # 원소 사용 여부를 체크
# check[k] 가 true 이면 인덱스가 k인 원소가 사용중임을 나타냄.
# check[k] 가 false 이면 인덱스가 k인 원소가 사용중이지 않음을 나타냄.
choose = [] # 나열한 원소를 보관

def permutation(level):
	if level == R:
		# 나열한 R 개의 원소를 출력
		print(choose)
		return

	# for문
	for i in range(0, N):
		if check[i] == True: # 인덱스가 i인 원소가 이미 사용중이라면 continue
			continue

		choose.append(lst[i]) # 인덱스가 i인 원소를 선택(추가) 
		check[i] = True # 인덱스가 i인 원소를 사용하고 있으므로 true로 초기화

		permutation(level+1) # 다음 for 문으로 들어가는 역할

		check[i] = False # 인덱스가 i인 원소의 사용이 끝났으므로 false로 초기화
		choose.pop() # (넣었던) 인덱스가 i인 원소를 제거


permutation(0)
- 시간 복잡도: $O(_nP_r)$
  • 조합 알고리즘
    • 조합의 모든 경우를 살펴보는 알고리즘
조합 알고리즘 코드 
N = 4
R = 3
lst = [1, 2, 3, 4]
choose = [] # 선택한 원소를 보관

def combination(index, level):
	if level == R:
		# 선택한 R 개의 원소를 출력
		print(choose)
		return

	# for문
	for i in range(index, N): 
		choose.append(lst[i]) # 인덱스가 i인 원소를 선택(추가)
		combination(i+1, level+1) # 다음 for 문으로 들어가는 역할
		choose.pop() # (넣었던) 인덱스가 i인 원소를 제거

combination(0, 0)
- 시간 복잡도: $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개를 고른 후에 나열한다고 생각해보자.
그러면, $_nC_r$은 모든 경우에 대해 나열하면(순서를 바꾸면) 된다.

Untitled.png

  • 따라서, nPr= nCr ⋅ r!_nP_r = \ _nC_r \ \cdot \ r! 이며, 이 수식을 정리하면 다음과 같다.
    • nCr=nPrr!_nC_r = \frac{_nP_r}{r!}