이번에 모회사 코테를 보는 데 내가 못풀었던 문제에서 중복순열을 2번사용하여 경우의 수를 구하는 브루트포스 방식의 문제가 출제 되었던 거 같다. 내가 생각한게 정답이 아닐 수 도 있지만 적어도 내가 생각한데로 풀기 위해서는 중복순열과 순열을 구현했어야 했다. 하지만 오랫동안 기본적인 알고리즘 조차 손을 놓았어서. 역시 급하게 준비한 코테답게 불합격 메일을 기다리고 있다. 확실히 불합격이 되더라도 코테를 직접 보면서 어떤 식으로 공부해야할지 감이 잡히기 시작했다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//중복 순열
int caseNum;
int arr[100000];
bool vectorIndexUsed[100000];
void DuplicatePermutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
DuplicatePermutation(level + 1, caseVector);
}
}
void Permutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
if (!vectorIndexUsed[i]) {
vectorIndexUsed[i] = true;
arr[level] = caseVector[i];
Permutation(level + 1, caseVector);
vectorIndexUsed[i] = false;
}
}
}
void Combination(int level, vector<int> caseVector, int beforeIndex) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = beforeIndex; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
Combination(level + 1, caseVector, beforeIndex + 1);
}
}
int main() {
cin >> caseNum;
vector<int> dupPermuTest = { 1,4,5,2 };
DuplicatePermutation(0, dupPermuTest);
cout << "====================================="<<endl;
Permutation(0, dupPermuTest);
cout << "====================================="<<endl;
sort(dupPermuTest.begin(), dupPermuTest.end());
Combination(0, dupPermuTest, 0);
}일단 기억나는 것은 주어진 벡터에서 몇명을 뽑아야하는 것이었다 이에 나는 중복순열,순열,조합순으로 현재 구현했다.
void DuplicatePermutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
DuplicatePermutation(level + 1, caseVector);
}
}중복 순열의 경우 똑같은 걸 여러번 사용해도 되니 굳이 사용했는지 안했는 지 체크할 필요가 없다
void Permutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
if (!vectorIndexUsed[i]) {
vectorIndexUsed[i] = true;
arr[level] = caseVector[i];
Permutation(level + 1, caseVector);
vectorIndexUsed[i] = false;
}
}
}순열의 경우 vector에서 순서가 다르면 다른것으로 인정하고 중복은 허하지 않는다
void Permutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
if (!vectorIndexUsed[i]) {
vectorIndexUsed[i] = true;
arr[level] = caseVector[i];
Permutation(level + 1, caseVector);
vectorIndexUsed[i] = false;
}
}
}조합은 중복을 허하지도 않고 순서가 달라도 같은 수를 뽑았으면 허용치 않는다.
void duplicateCombination(int level, vector<int> caseVector, int beforeIndex) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = beforeIndex; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
duplicateCombination(level + 1, caseVector, i);
}
}중복 조합은 같은 수를 뽑을 수 있고 순서가 존재한다 이에 같은수는 뽑을 수 있지만 순서가 다르고 동일한 요소로 이루어져있는 것은 이전에 뽑은것과 같음으로 허용치 않는다
이 정도 문법은 꼭 기억하도록 하자
