4. 순열 알고리즘 구현해보기 (BOJ 10974)

순열 알고리즘이란?

n개의 원소 중에서 r개를 나열하는 모든 경우를 살펴보는 알고리즘입니다. 조합 알고리즘과 다른 점은 순열은 순서의 개념이 존재하므로 [1, 3, 2]와 [2, 1, 3]의 경우의 수를 다른 경우로 취급하고 센다는 것입니다.

공식 : ${}_n{P}_r=n\cdot (n-1)\cdots (n-r+1)$

예시 : [1, 2, 3, 4, 5] 5개 중 3개를 뽑는 조합은 ${}_5{P}_3$으로 나타낼 수 있습니다. 경우의 수들은 아래와 같습니다.

[1, 2, 3] -> 순서 다른 [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
[1, 2, 4] -> 여기도 순서 다른 5가지
[1, 2, 5] -> 여기도 순서 다른 5가지
[1, 3, 4] -> 여기도 순서 다른 5가지
[1, 3, 5] -> 여기도 순서 다른 5가지
[1, 4, 5] -> 여기도 순서 다른 5가지
[2, 3, 4] -> 여기도 순서 다른 5가지
[2, 3, 5] -> 여기도 순서 다른 5가지
[2, 4, 5] -> 여기도 순서 다른 5가지
[3, 4, 5] -> 여기도 순서 다른 5가지

$5\cdot 4\cdot 3$의 계산 과정을 통해 총 60개의 결과가 나옵니다.

---

문제

BOJ 10974 문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

---

풀이

풀이1. 재귀함수 활용하여 직접 구현

함수 이해하기

재귀함수를 활용하여 배열의 순열들을 구한 과정에 대해 이해해야 합니다. 아래 예시 함수를 확인해봅시다.

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)

이해해보기

level은 현재 재귀 호출의 깊이를 나타내며, 이는 선택된 숫자의 개수와 같습니다.
choose 리스트는 현재까지 선택된 숫자로 구성된 부분 순열을 저장하며, check 리스트는 특정 숫자가 이미 선택되었는지를 나타냅니다.
순열을 만들기 위해 1부터 N까지의 숫자를 하나씩 확인하면서, 아직 선택되지 않은 숫자를 choose에 추가하고 check 배열을 업데이트한 후 재귀 호출을 통해 다음 숫자를 선택합니다.
만약 level == N이 되면, choose 리스트에 N개의 숫자가 모두 채워진 것이므로 이를 출력합니다.
이후, 백트래킹을 수행하여 마지막으로 추가된 숫자를 choose에서 제거하고 check 배열을 복구하여 다른 숫자로 새로운 조합을 생성할 수 있도록 합니다.

문제 풀이 결과

def permutation(level):
    global N, choose, check
 
    # base case
    if level == N:
        print(' '.join(map(str, choose)))
        return
 
    # recursive case
    for i in range(1, N + 1):
        if check[i] == True:
            continue
 
        choose.append(i)
        check[i] = True
 
        permutation(level + 1)
 
        check[i] = False
        choose.pop()
 
 
N = int(input())
choose = []
check = [False] * (N + 1)
 
permutation(0)

풀이2. permutations 라이브러리 사용하기

permutations 함수 알아보기

파이썬의 itertools 모듈에 포함된 함수이며 순열을 생성해주는 함수입니다.

• permuatations(arr, num)
  • arr: 배열을 의미
  • num: 뽑을 개수를 의미

문제 풀이 결과

from itertools import permutations
 
 
N = int(input())
 
for permutation in permutations(range(1, N + 1)):
    print(' '.join(map(str, permutation)))