Search

순열 알고리즘 [개념]

생성일
2024/07/12
[06강] 순열 알고리즘
안녕하세요 Gliver 입니다. 이번 글에서는 순열 알고리즘에 대해 알아보겠습니다. 목차 순열 알고리즘 실제 문제에서 순열 알고리즘 '순열(Permutation)과 조합(Combination)의 차이점'은 이전 글(조합 알고리즘)에서 설명했기 때문에 생략하겠습니다. 순열 알고리즘 순열은 수식으로 나타내면 nPr 입니다. 즉, 순열의 수식은 전체 원소의 개수 n 과 나열할 원소의 개수 r 로 구성되어 있습니다. 순열 알고리즘 순열 알고리즘은 n개의 원소 중에서 r개를 나열하는 모든 경우에 대해 살펴보는 알고리즘입니다. 예를 들어, 1~11의 숫자가 있고 이 중에서 2개를 나열하는 경우라고 하면 $_{11}\mathrm{P}_{2}(110)$가지 경우에 대해 살펴보는 거임. 순열 알고리즘은 원소 n개 중에서..
https://gliver.tistory.com/14

1. 순열 알고리즘

•
조합과 순열의 차이
◦
조합은 순서라는 개념이 존재하지 않음.
◦
순열은 순서라는 개념이 존재함
조합과 순열 예시
•
순열 알고리즘이란?
◦
순열 알고리즘: nn개의 원소 중에서 rr개를 나열하는 모든 경우를 살펴보는 알고리즘
◦
순열 알고리즘을 구현하는 방법
1.
for문을 이용
: for 문을 이용하면 for문을 rr개 사용해야 하므로 확장성이 좋지 않다.
2.
재귀함수를 이용
: 재귀함수를 이용하면 rr을 인자로 받아 처리할 수 있어 확장성이 좋다.
◦
순열 알고리즘의 시간 복잡도
▪
순열 알고리즘은 nn개의 원소 중에서 rr개를 나열하는 모든 경우를 살펴본다.
▪
따라서, 시간 복잡도는 O(nPr)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)
Python
복사
◦
check 배열: 원소의 사용 유무를 확인하기 위한 배열
◦
level: 현재 선택한 원소의 개수 (깊이를 의미)
◦
현재 선택한 원소(level)가 R이면, 그때 R만큼 나열한 것이니 처리해 주면 된다.