이 글에서는 숫자 N이 주어졌을 때 Alexander Bogomolny의 비정렬 순열 알고리즘(UnOrdered Permutation Algorithm)을 사용해 N의 모든 순열을 찾는 방법을 알아봅니다.
순열(Permutation)이란?
순열이란 집합에 속한 원소들을 고유한 순서로 배열하는 방법의 수를 의미합니다.
예시 — {4, 9, 2}의 순열은 {4,9,2}, {4,2,9}, {9,4,2}, {9,2,4}, {2,4,9}, {2,9,4}로 총 6가지입니다. 원소가 3개일 때 순열의 개수는 3! = 6으로 계산할 수 있습니다.
순열은 컴퓨터 네트워크에서 스위칭 네트워크를 정의하거나 병렬 처리를 설계할 때 활용되며, 다양한 암호화 알고리즘에서도 널리 사용됩니다.
Alexander Bogomolny의 비정렬 순열 알고리즘이란?
이 알고리즘은 첫 N개의 자연수(1부터 N까지)로 만들 수 있는 모든 가능한 순열을 계산합니다. 숫자 N이 주어지면 1부터 N까지의 수를 이용해 모든 순열을 생성합니다.
입력 / 출력 예시
입력
N = 3
출력
1,2,3 ; 1,3,2 ; 2,1,3 ; 2,3,1 ; 3,1,2 ; 3,2,1
알고리즘 동작 방식
- 배열, 숫자 N, 정수 k를 매개변수로 받는 함수를 작성합니다.
- 레벨(level) 변수를 초기화하고, 레벨이 증가할 때마다 나머지 값들을 순열화합니다.
- 재귀 종료 조건(레벨 == N)에 도달하면 해당 순열의 모든 값을 출력합니다.
이 알고리즘의 핵심은 전역 변수 level과 배열을 활용한 백트래킹(backtracking) 기법입니다. 각 재귀 호출에서 아직 사용되지 않은 값(배열에서 0으로 남아 있는 위치)을 찾아 다음 레벨로 진행하고, 하나의 순열이 완성되어 출력된 후에는 값을 되돌려 놓음으로써 다른 조합을 계속 탐색합니다.
C++ 구현 코드
위 알고리즘을 구현한 프로그램은 다음과 같습니다.
#include <iostream>
using namespace std;
int level = -1;
void AlexanderBogomolyn(int permutations[], int N, int k) {
level = level + 1;
permutations[k] = level;
if (level == N) {
for (int i = 0; i < N; i++)
cout<<permutations[i]<<"\t";
cout<<endl;
}
else{
for (int i = 0; i < N; i++)
if (permutations[i] == 0)
AlexanderBogomolyn(permutations, N, i);
}
level = level - 1;
permutations[k] = 0;
}
int main(){
int N = 4;
int permutations[N] = { 0 };
cout<<"All permutations are :\n";
AlexanderBogomolyn(permutations, N, 0);
return 0;
}실행 결과
All permutations are : 1 2 3 4 1 2 4 3 1 3 2 4 1 4 2 3 1 3 4 2 1 4 3 2 2 1 3 4 2 1 4 3 3 1 2 4 4 1 2 3 3 1 4 2 4 1 3 2 2 3 1 4 2 4 1 3 3 2 1 4 4 2 1 3 3 4 1 2 4 3 1 2 2 3 4 1 2 4 3 1 3 2 4 1 4 2 3 1 3 4 2 1 4 3 2 1
마무리
Alexander Bogomolny의 비정렬 순열 알고리즘은 재귀 호출과 백트래킹을 결합해 N개의 자연수로 만들 수 있는 모든 순열을 체계적으로 생성합니다. 생성해야 할 순열의 개수 자체가 N!이므로 시간 복잡도는 O(N × N!)이 되며, 이는 모든 순열을 출력해야 하는 문제에서 사실상 피할 수 없는 최소 비용입니다. 재귀 구조와 백트래킹의 동작 원리를 이해하는 좋은 학습 예제이므로, 직접 코드를 실행하며 level 값과 배열의 변화를 추적해 보면 알고리즘에 대한 이해를 크게 높일 수 있습니다.