1. 순열 알고리즘

조합과 순열의 차이
- 조합은 순서라는 개념이 존재하지 않음.
- 순열은 순서라는 개념이 존재함

조합과 순열 예시

순열 알고리즘이란?
- 순열 알고리즘: $n$ 개의 원소 중에서 $r$ 개를 나열하는 모든 경우를 살펴보는 알고리즘
- 순열 알고리즘을 구현하는 방법
  1. for문을 이용 👎
    
    : for 문을 이용하면 for문을 $r$ 개 사용해야 하므로 확장성이 좋지 않다.
  2. 재귀함수를 이용 👍
    
    : 재귀함수를 이용하면 $r$ 을 인자로 받아 처리할 수 있어 확장성이 좋다.
- 순열 알고리즘의 시간 복잡도
  - 순열 알고리즘은 $n$ 개의 원소 중에서 $r$ 개를 나열하는 모든 경우를 살펴본다.
  - 따라서, 시간 복잡도는 $O(_nP_r)$ 이라고 할 수 있다.

2. 순열 알고리즘 구현 (재귀함수)

재귀함수를 이용하여 순열 알고리즘 구현

N = 10
R = 3
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
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)

check 배열: 원소의 사용 유무를 확인하기 위한 배열
level: 현재 선택한 원소의 개수 (깊이를 의미)
현재 선택한 원소(level)가 R이면, 그때 R만큼 나열한 것이니 처리해 주면 된다.

순열 알고리즘 [개념]

1. 순열 알고리즘

2. 순열 알고리즘 구현 (재귀함수)

Command Palette

Choose Theme