은근 헷갈리는 알고리즘 - 순열 (Permutation)알고리즘

1. Introduction

순열이란, 어떤 데이터들에 대해서 해당 데이터로 줄을 세우는 것을 말한다.

예를 들어, (1,2,3) 에 대한 순열은 다음과 같다.

(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) 

필자는 알고리즘에서 순열을 처음 배울 때 재귀로 푼다는 말을 듣고도 틀렸고, 나중에 시간이 한참지나서 시험칠 때 다시 공부했을 때도 틀렸고, 지금 포스팅할때도 틀렸다...

 

이런 젠장

---

2. Approach

앞서 설명했듯, 순열은 재귀로 푼다. 다만 그 과정이 쉽게 머리에 박히지 않아서 그림을 통한 설명이 필요하다.

아래 그림은 순열을 구하는 과정을 시각화한 것이다. 사전순으로 얻는 과정을 (즉, 결과가 뒤에서 부터 swap됨) 앞에서 부터 순서대로 고정한다는 개념으로 설명하고 있다[출처].

Process on Permutation

---

3. Implementation

다음은 순열을 출력하는 코드이다. 위의 개념에서 i와 n이 같을 때만 출력한다는 부분만 추가되었다.

def perm(arr, i, n):
    if i == n:
        print(arr)
    else:
        for j in range(i, n+1):
            arr[i], arr[j] = arr[j], arr[i]
            perm(arr, i+1, n)
            arr[i], arr[j] = arr[j], arr[i]
            
            

arr = list(range(1, 4))

perm(arr, 0, 2)

---

4. Discussion

문제는 이 알고리즘의 시간복잡도인데, 배경지식이 좀 있는 사람들은 ${}_n\mathrm{P}_{r} = {n! \over (n-r)!}$이니까 $O(n!)$이라고 말하겠지만, 사실 더 나온다.

• $T_{perm}(0, n) = (n+1) * T_{perm}(1, n)$
• $T_{perm}(1, n) = n * T_{perm}(2,n)$
• $T_{perm}(n, n) = n + 1$
• $\therefore T_{perm}(0, n) = (n + 1) * n * (n - 1) * ... * 1 * (n + 1) = (n + 1) * n! * (n + 1)$

따라서, 위의 식에 따라 시간복잡도가 $O(n^2n!)$이 나온다. 그냥 $O(n!)$도 $O(2^n)$을 뛰어넘는 괴물인데 그것보다 한참 더 느리다.