C++를 이용하면 사용자가 지정한 길이(M)의 암호를 여러 개(N개) 손쉽게 생성할 수 있습니다. 이 프로그램은 먼저 rand() 함수로 0~9 사이의 난수를 만든 뒤, 순열(permutation) 알고리즘과 백트래킹 기법을 적용해 해당 숫자들의 다양한 조합을 암호로 출력합니다.
알고리즘
프로그램의 핵심 동작 흐름은 아래 의사코드(pseudo-code)와 같습니다.
Begin
암호의 길이를 입력받는다.
permutation() 함수가 무작위 암호를 생성한다.
/* 매개변수 설명
a : 정수 배열의 포인터
m : 현재 교환 기준 위치
s : 암호의 전체 길이
*/
// 함수 본문
if (m == s)
i = 0 ~ s-1 반복
*(a + i) 출력
else
i = m ~ s-1 반복
int tmp = a[m]
a[m] = a[i] // 두 원소 교환
a[i] = tmp
permutation(a, m + 1, s) 호출 // 재귀 호출
tmp = a[m]
a[m] = a[i] // 원상 복구(백트래킹)
a[i] = tmp
End
예제 코드
다음은 위 알고리즘을 실제로 구현한 C++ 전체 소스 코드입니다.
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
void permutation(int *a, int m, int s) {
if (m == s) {
for (int i = 0; i < s; i++) {
cout << *(a + i);
}
cout << endl;
} else {
for (int i = m; i < s; i++) {
int tmp = a[m];
a[m] = a[i];
a[i] = tmp;
permutation(a, m + 1, s);
tmp = a[m];
a[m] = a[i];
a[i] = tmp;
}
}
}
int main(int argc, char **argv) {
cout << "Enter the length of the password: ";
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
a[i] = rand() % 10; // 난수 생성
}
cout << "Random Numbers are:" << endl;
for (int i = 0; i < n; i++) {
cout << a[i] << endl;
}
cout << "The Passwords are: " << endl;
permutation(a, 0, n);
}
실행 결과
Enter the length of the password: 4 Random Numbers are: 1740 The Passwords are: 1740 1704 1470 1407 1047 1074 7140 7104 7410 7401 7041 7014 4710 4701 4170 4107 4017 4071 0741 0714 0471 0417 0147 0174
코드 동작 원리
프로그램의 실행 과정을 단계별로 살펴보면 다음과 같습니다.
1. 난수 생성
main() 함수에서 사용자에게 암호 길이를 입력받은 후, rand() % 10을 이용해 0부터 9까지의 숫자를 길이만큼 배열에 저장합니다. 예제에서는 길이 4를 입력했으므로 "1740"이라는 네 자리 난수가 생성되었습니다.
2. 순열 생성과 백트래킹
permutation() 함수는 재귀적으로 각 위치의 숫자를 서로 교환(swap)하며 가능한 모든 배치를 탐색합니다. 한 번의 재귀 호출이 끝나면 교환했던 원소를 다시 원래대로 되돌리는 백트래킹(backtracking) 과정을 거치기 때문에, 중복 없이 모든 순열을 빠짐없이 출력할 수 있습니다.
3. 결과 확인
길이가 4일 때 만들 수 있는 순열의 개수는 4! = 24개입니다. 실행 결과에서도 정확히 24개의 서로 다른 암호가 출력된 것을 확인할 수 있습니다.
참고로 #include<conio.h>는 콘솔 입출력 보조 헤더로, 일부 컴파일러 환경에서만 지원됩니다. 표준 환경에서 실행할 때는 해당 줄을 제거해도 프로그램 동작에는 문제가 없습니다.