[알고리즘] 순열(Permutation)

1. 수학에서의 순열(Permutation)

2. 순열 알고리즘이란?

3. 순열 알고리즘 - 재귀

4. 순열 알고리즘 - 반복

5. 시간 복잡도

수학에서의 순열(Permutation)

순열은 서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수이다.

 

만약 r이 n이라면, 다음과 같이 수식으로 간단히 n! 이라고 표현할 수 있다.

r이 임의의 값이라면, 수식은 다음과 같다.

n: 전체 원소의 개수

r: 선택하여 나열할 원소의 개수

n!: n의 팩토리얼, 즉 n × (n-1) × (n-2) × ⋯ × 1

(n - r)!: 선택하지 않은 나머지 원소들의 수에 대한 팩토리얼

 

예를 들어, 5개의 원소 중 3개를 선택하여 나열하는 순열 수는 다음과 같다.

즉, 5개의 원소에서 3개를 선택하여 나열하는 경우는 60가지이다. 

순열 알고리즘이란?

순열 알고리즘은 주어진 원소들의 모든 간으한 나열 방법을 생성하는 알고리즘이다. 순열은 순서를 고려해 원소를 나열하는 것이기 때문에 각 원소의 위치를 변경하여 가능한 모든 경우를 탐색하는 것이 핵심이다. 일반적으로, 순열을 생성하는 방식은 재귀나 반복을 사용하여 원소들을 교환하거나, 순차적으로 나열하며 모든 가능한 순열을 생성하는 방식으로 동작한다.

1. 순열 알고리즘 - 재귀(Recursion) 

순열을 생성하는 가장 일반적인 방식은 재귀적 방법이다. 이 방식은 하나의 원소를 고정한 후, 나머지 원소들로 순열을 만들어 결합하는 방식이다. 여기에 사용되는 대표적인 알고리즘은 백트래킹 방식이다. 

 

{a, b, c} 예시로 순열을 만들어보자.

1. 첫 번째 자리에 a를 고정하고 나머지 {b, c}의 순열을 만든다. 
   • {a, (b, c)} -> {a, b, c}, {a, c, b}
2. 첫 번째 자리에 b를 고정하고 나머지 {a, c}의 순열을 만든다.
   • {b, (a, c)} -> {b, a, c}, {b, c, a}
3. 첫 번째 자리에 c를 고정하고 나머지 {a, b}의 순열을 만든다.
   • {c, (a, b)} -> {c, a, b}, {c, b, a}

이 과정에서 다음과 같이 모든 가능한 순열이 생성된다.

{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}

C++ 구현 코드 (재귀)

핵심 아이디어는 다음과 같다.

• 종료 조건
  • 재귀 호출에서 loc이 배열의 끝에 도달할 경우, 배열에 대한 순열이 완성된 것이므로 출력한다.
• 교환과 백트래킹
  • 순열 생성 과정에서는 현재 위치의 원소와 이후의 원소들을 하나씩 교환하면서 새로운 순열을 생성한다. 
  • 재귀 호출이 끝나면 원래 상태로 되돌려놓아야 하므로 교환을 다시 한 번 수행한다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 순열을 출력하는 함수
void printPermutation(vector<int>& arr) {
    for (int i : arr)
        cout << i << " ";
    cout << endl;
}

// 재귀적으로 순열을 생성하는 함수
void generatePermutation(vector<int>& arr, int loc) {
    if (loc == arr.size() - 1) {
        printPermutation(arr);  // 순열이 완성되면 출력
        return;
    }

    for (int i = loc; i < arr.size(); i++) {
        swap(arr[loc], arr[i]);           // 원소 교환
        generatePermutation(arr, loc + 1); // 다음 위치로 이동
        swap(arr[loc], arr[i]);           // 원래 상태로 복원 (백트래킹)
    }
}

int main() {
    vector<int> arr = {1, 2, 3};
    generatePermutation(arr, 0);  // 순열 생성 시작
    return 0;
}

2. 순열 알고리즘 - 반복(next_permutation) 

재귀를 사용하지 않고, next_permutation 함수를 이용해 반복적으로 순열을 생성할 수도 있다. 

C++ 구현 코드 (반복)

핵심 아이디어는 다음과 같다.

• next_permutation 함수를 사용해서 현재 배열을 다음 순열로 변경한다.
• 배열을 처음 정렬된 상태로 두고 next_permutation을 반복 호출하여 모든 가능한 순열이 사전 순으로 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	vector<int> arr = {1, 2, 3};
    
    // 모든 순열을 생성
    do {
    	for (int i: arr) cout << i << " ";
        cout << endl;
    } while(next_permutation(arr.begin(), arr.end())); // 다음 순열을 생성
    
    return 0;
}

 

위 두 소스 코드의 출력 결과는 다음과 같습니다.

시간 복잡도

순열을 생성하는 알고리즘의 시간 복잡도는 O(n!)이다. n개의 원소로 만들 수 있는 순열의 가짓수가 n!개이기 때문이다.

따라서, 원소의 개수가 많아질수록 순열을 모두 탐색하는 것은 오래걸릴 수 있다. 그렇기 때문에 보통은 원소의 수가 적을 때 사용된다.