순열
알고리즘에서 "순열"은 주어진 원소들을 모든 가능한 순서대로 배열하는 경우의 수를 의미합니다. 다시 말해, 주어진 원소들의 순서를 변경하여 만들 수 있는 모든 경우의 배열을 나타내는 것입니다. 예를 들어, 3개의 원소 A, B, C에 대한 순열은 ABC, ACB, BAC, BCA, CAB, CBA와 같이 가능한 모든 순서의 배열을 나타냅니다.
순열은 조합과 함께 주어진 원소들의 가능한 조합을 나타내는 개념입니다. 순열은 다양한 문제와 알고리즘에서 사용되며, 주로 다음과 같은 분야에서 활용됩니다:
- 조합 최적화 문제: 문제의 조건에 따라 원소들의 순서가 중요한 경우에 순열을 활용하여 최적화 문제를 해결할 수 있습니다.
- 문자열 조합: 문자열 내의 문자들의 모든 가능한 배열을 생성하거나 검사하는 작업에 활용됩니다.
- 탐색 공간 줄이기: 순열을 이용하여 가능한 경우의 수를 줄이고 더 효율적으로 탐색하는 알고리즘을 개발할 수 있습니다.
순열을 생성하는 방법은 여러 가지가 있습니다. 재귀적인 방법, 반복적인 방법, 비트 연산 등을 사용하여 순열을 생성할 수 있습니다. 주어진 원소의 개수가 작을 경우에는 모든 가능한 순열을 생성하는 것이 가능하지만, 원소의 개수가 많을 경우에는 연산량이 기하급수적으로 증가하기 때문에 주의가 필요합니다.
여러 가지 알고리즘 문제나 프로그래밍 대회에서 순열과 관련된 문제들을 만날 수 있으며, 이를 효율적으로 다루기 위해 순열을 생성하고 처리하는 알고리즘에 대한 이해가 필요합니다.
#include <iostream>
#include <vector>
using namespace std;
void Permutation(vector<bool> visited, vector<char> arr, vector<char> perm, int depth) {
if (depth == perm.size()) { // 깊이가 목표 배열 크기까지 왔으면 멈춤
// 3의 크기를 받아야했을 떄 depth와 perm.size()가 같으면 멈춤
for (int i = 0; i < perm.size(); i++) { // 하나씩 출력
cout << perm[i] << " ";
}
cout << endl;
return;
}
for (int i = 0; i < arr.size(); i++) { // 전체 배열 사이즈 만큼 돌면서
if (visited[i]) // 혹시 그곳을 방문 했으면 넘어가
continue;
visited[i] = true; //방문 안했으면 방문 체크해서 더 이상 방문 못하게 고정
perm[depth] = arr[i]; // depth에 값 삽입
Permutation(visited, arr, perm, depth + 1);
visited[i] = false; // 재귀다 돌고오면 다시 해당 원소 사용가능하게 풀어줌
}
}
int main() {
vector<char> vec = { 'a','b','c', 'd','e' };
const int n = vec.size();
const int r = 2;
vector<char> perm(r);
vector<bool> visited(n);
Permutation(visited, vec, perm, 0);
return 0;
}