순열과 조합...
알고리즘 공부할 때마다 헷갈려서 한번 정리하고 갑니다.
고등학생때 확률과 통계 배우면서 년단위로 배웠는데도 정작 필요할때 다시 공부하고 가야하는 모습에
안타깝습니다... 이번엔 진짜 까먹지 말아야지.
순열: 순서가 있게 선택 (EX. 각 팀별 공연순서 정하기)
예를 들어 5개 팀이 참가하는 페스티벌이 있습니다.
이 페스티벌에서 오늘 공연장 대여시간상 2팀이 공연을 할 수 있기 때문에 순서대로 2팀이 공연한다고 생각해봅시다.
순서가 있기 때문에 오늘 공연할 팀을 정한 순서표는 순열입니다!
경우의 수도 계산해볼까요?
첫번째 공연할 팀을 하나 뽑을 거고 이때 경우의 수는 5팀 중에서 한 팀을 뽑습니다.
두번째로 공연할 팀은 아까 공연한 팀을 제외한 4팀 중에서 한 팀을 뽑습니다!
따라서 순서가 있게 5팀 중 2팀을 뽑는 경우의 수는 5*4로 20이 나오게 됩니다!
조합: 순서 상관없이 선택 (EX. 로또 숫자 정하기)
예를 들면 로또 숫자를 정하는 게 있습니다.
0, 1, 2, 3, 4
이러한 5개의 숫자 중 2개의 숫자를 맞추는 임의의 간이 로또가 있다고 생각합시다.
이때 (0, 3)을 고르던 (3, 0)을 고르던 로또를 맞췄는지 여부는 바뀌지가 않습니다.
즉, 순서가 상관없기 때문에 이 숫자열은 조합입니다!
경우의 수를 계산해볼까요?
일단 하나를 골라봅시다! 5개중 1개를 뽑습니다.
두번째는 아까 뽑은 숫자를 제외한 4개중 1개를 뽑습니다!
여기까지는 아까 순열과 경우의 수가 같죠?
그렇습니다 이렇게 고른 숫자열은 순서가 존재하는 친구들입니다!
(0, 3)과 (3, 0)같은 중복을 제거해주어야 합니다.
2개의 숫자를 순서대로 세우는 경우의 수는? 2!입니다
2!로 나누어 주면됩니다! (왜냐하면 같은 숫자를 사용한 조합이 순서대로 세운만큼 존재할 것이기 때문이죠)
따라서 (5*4)/2! = 10 으로
5개 숫자 중 2개의 로또번호를 뽑는 경우는 총 10가지 경우가 존재합니다!
이젠 코드로 가볼까요!
0~4까지의 숫자중 2개의 숫자를 순서상관있게(= 순열)골라 출력해주는 코드를 짜봅시다.
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<int> permute;
const int perSize = 2;
const int preInpSize = 5;
int preInpNum[preInpSize] = {0,1,2,3,4};
int visited[preInpSize];
void printPermute(vector<int>& perm){
printf("(");
for(int i = 0; i < perm.size();i++){
if(i)printf(", ");
printf("%d",perm[i]);
}
printf(")\n");
}
void makePermute(vector<int>& perm){
if(perm.size() == perSize){
printPermute(perm);
return;
}
for(int i = 0; i < preInpSize; i++){
if(!visited[i]){
perm.push_back(preInpNum[i]);
visited[i] = 1;
makePermute(perm);
permute.pop_back();
visited[i] = 0;
}
}
return;
}
int main(){
memset(visited,0,sizeof(visited));
makePermute(permute);
}순열을 만들어주는 함수인 makePermute가 핵심입니다!
현재 순열에 미리 주어진 숫자열중 아직 추가가 안된 숫자(visited[X] == 0인)를 추가하고 현재 순열이 지정한 순열의 크기(perSize)에 도달하면 출력하는 식으로 동작합니다.
해당 함수는 재귀적으로 동작하며 순열을 만들어 나갑니다!
이번엔
1~5까지의 숫자 중 3개의 숫자를 순서 상관없이(= 조합) 고르는 코드를 작성해 봅시다.
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<int> combination;
const int combSize = 3;
const int preInpSize = 5;
int preInpNum[preInpSize] = {1,2,3,4,5};
void printVector(vector<int>& vec){
printf("(");
for(int i = 0; i < vec.size();i++){
if(i)printf(", ");
printf("%d",vec[i]);
}
printf(")\n");
}
void makeCombi(int now,vector<int>& combi){
if(now > preInpSize) return;
if(combi.size() == combSize){
printVector(combi);
return;
}
for(int i = now; i < preInpSize; i++){
combi.push_back(preInpNum[i]);
makeCombi(i+1,combi);
combi.pop_back();
}
return;
}
int main(){
makeCombi(0,combination);
return 0;
}makeCombi 부분 이외에는 대부분의 코드가 순열 생성코드와 비슷합니다!
위 사진과 같이 순회하며 조합을 생성하게 됩니다!
코드의 오류나 이해가 안가는 부분은 댓글에 남겨주시면 피드백 하도록 하겠습니다!
그럼 20000~ 총총