알고리즘 개념 정리글입니다. 이해가 힘드신 부분이거나, 명확하지 않은 부분에 대한 피드백은 언제나 환영합니다!
순열
순열은 개념자체는 간단하다. , n개 중 r개를 뽑아서 순서대로 나열하는 모든 경우의 수를 "순열"이라고 한다.
예를들어, A,B,C 3명의 사람이 있을 때, 2명을 뽑아서 줄 세우는 경우의 수를 구한다고 하면,
(A,B),(A,C) ,(B,A),(B,C),(C,A),(C,B) 로 모두 6가지 경우의 수가 생긴다.
이 과정을 쉽게 개념화 하는 방법은 2자리가 있다고 생각해보자.한 자리마다 올 수 있는 경우의 수를 따져서 동시에일어나므로 곱셈을 해주는 일명 곱의법칙을 적용해서 쉽게 풀어내는 방식이 있다.
이 과정을 공식화 시킨게 이다. n개 만큼의 자리가 있다고 생각하고, 먼저 n개만큼을 줄세우고, 중복되는 것들은 똑같다고 생각해서 제외해주는 방식이다.
*증명까지 적으려면 , 수학시간이 되어버리기 때문에, 최대한 순열에 의미에 집중하게끔 풀어썼다.
한줄정리
순열(Permutation)은 n개 중에서 r개를 뽑아서 , 줄 세우는 경우의 수이다.
뜬금없이 왜 순열의 정의를 ?
순열의 의미를 아는게 중요하지 않을 수 있다. 하지만, 개인적으로 생각하는 코딩은 "어떤 의미를 가진 친구를 전자세계에 표현을 어떻게 잘 해줄것이냐"라고 생각 하기 때문에, 표현하려는 대상의 본질적인 의미 를 잘 알아야한다고 생각한다.
순열 구현하기
순열을 구현하는 방법은 아주 많을 수 있다. 특히, 단순히 경우의 수를 구한다면 , Facotrial만으로 구할 수 있기 때문에, 아주 간단해진다. nPr이라고 했을 때, 아래와 같이 간단하게 구현할 수 있다. (OverFlow가 매우매우 잘 나는 예제이지만, 일단은 int를 쓴다고 가정했을 때)
#include<bits/stdc++.h>
using namespace std;
int Factorial(int n){
if( n==0 || n==1)
return 1;
return n *Factorial(n-1);
}
int main(){
int n,r;
int res;
cin >>n >>r;
res = Factorial(n)/Factorail(n-r)
return 0;
}위 코드의 단점은 간단하다. 경우의 수밖에 못구할 뿐더러, Factorial 계산자체가 4byte의 범위에서 표현할 수 있는 범위를 아주 쉽게 뛰어넘기 때문에, 한정적인 숫자 내에서만 동작한다.
(물론, long long, int64와 같은 범위를 늘리는 방법을 사용할 수 있습니다)
모든 순열의 경우의 수를 구해보자
순열을 구한다면 (1,2),(2,1)...과 같이 모든 경우의 수를 출력하고 싶을 수 있다. 그런 코드는 어떻게 짤 수 있을까?
Swap 이용하기
Permutation의 모든 경우를 구할 때, 직접 하나씩 구하다보면 알 수 있는 규칙이 있다.
(A,B,C)의 모든 경우의 수를 구한다고 생각해보자. (A,B,C) ,(A,C,B) ,(B,A,C) ,(B,C,A),(C,A,B), (C,B,A)
(A,B,C)와 (A,C,B)를 보면 알 수 있는게 있다. 바로, A를 먼저 뽑아놓고, B,C의 자리를 바꾸는 경우를 구해주면 된다. 마찬가지로, B도 B를 먼저 뽑고, (A,C),(C,A)를 바꿔주면 된다. 즉 , 교체를 해주는 개념으로 순열을 구현하겠다는 이야기이다.
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int n, r;
void printV(vector<int> &v)
{
for (int i = 0; i < r; i++)
{
cout << v[i] << ' ';
}
cout << "\n";
}
void Permutation(int n, int r, int depth)
{
if (depth == r)
{
printV(v);
return;
}
for (int i = depth; i < n; i++)
{
swap(v[i], v[depth]);
Permutation(n, r, depth + 1);
swap(v[i], v[depth]);
}
}
int main()
{
cin >> n >> r;
for (int i = 0; i < n; i++)
v.push_back(i);
Permutation(n, r, 0);
return 0;
}실행결과
- 어, 면, (1,2),(1,3)..과 같이 결과가 나와야하는 것 아닌가요? 할 수 있는데, 위에서 vector은 배열의 Index를 뽑은 것이다. 즉, 어떤 배열이 있다면
int A[] ={1,2,3}0번째 인덱스 요소와 1번째 인덱스 요소, (1,2), 0번째 인덱스 요소와 2번째 인덱스 요소 (1,3), 와 같이 응용을 할 수 있게 된다.
방문체크 해주기
이번에는 방문을 기록하며 순열을 만들어볼 수도 있다. 예를들어, 3!를 구한다고 했을 때,
(1,2,3),(1,3,2)와 같은 순열을 만들어낼 때, 1번 방문 -> 2번방문 -> 3번방문 ,
1번 방문 ->3번방문 -> 2번방문과 같이, 방문을 했냐/하지않았냐의 기준으로 반복문을 설정해서 Permutation을 만들 수 있다.
#include <bits/stdc++.h>
using namespace std;
void PrintVector(vector<char> result)
{
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
}
void Permutation(vector<int> arr, vector<char> result, vector<bool> used, int depth)
{
if (depth == result.size()) // r일때
{
PrintVector(result);
cout << "\n";
return;
}
for (int i = 0; i < arr.size(); i++)
{
if (used[i] == true)
continue;
// cout << "Depth:" << depth << '\n';
used[i] = true;
result[depth] = arr[i] + '0';
// cout << "result[depth]:" << result[depth] << '\n';
Permutation(arr, result, used, depth + 1);
used[i] = false;
}
}
int main()
{
int n, r;
cin >> n >> r;
// 배열 , 방문체크
vector<int> arr(n);
vector<bool> used(n);
// 결과
vector<char> result(r);
// 1~N까지 배열 생성
for (int i = 0; i < n; i++)
{
arr[i] = i + 1;
}
Permutation(arr, result, used, 0);
return 0;
}