급하게임개발

https://www.acmicpc.net/problem/15663

이 문제는 N과 M 문제 중에 어려운 쪽에 속했다 이에 풀기 위해서는 기본적인 백트래킹 알고리즘을 사용하데 조건을 잘 맞춰주어야했다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int beforearr[8] = { 0, };
int arr[8];
int answer[8];
bool isused[8];
int cnt;
void solution(int level) {
	if (level == M) {
		for (int i = 0; i < M; i++) {
			cout << answer[i] << " ";
		}
		cout << endl;
		return;
	}
	int finalusing = 0;
	for (int i = 0; i < N; i++) {
		if (!isused[i] && finalusing!=arr[i] ){
			answer[level] = arr[i];
			finalusing = answer[level];
			isused[i] = true;
			solution(level + 1);
			isused[i] = false;
		}
	}

}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	solution(0);

}

이 문제를 해결하는 방법이다 이 문제의 경우 백트래킹을 사용하기 위해 일단 입력받은 배열을 오름차순으로 정렬을 해주면 같은 level내에서 같은 값을 뽑아서 사용하게 되면 똑같은 수열이 나오기에 스택에서 바로 이전에 썼던 값만 안써주면 중복을 피할 수 있다 예를 들어 1 7 9 9 로 나열되어 있으면 1번째 9가 사용되면 2번째 9는 사용되지 않기 위함이다 1번째 9를 사용할때는 이전에는 7을 사용했으므로 사용할 수 있지만 2번째 9의 경우 1번째 9를 이전에 사용했으므로 사용할 수 없다 즉 바로 이전에 사용한 값을 final using이라는 변수에 넣고 이를 이용해서 앞으로 넣을 값이 중복되면 넣지 않도록 작성한다. 생각하기가 좀 까다로운 문제였던것 같다

이번에 모회사 코테를 보는 데 내가 못풀었던 문제에서 중복순열을 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);
	}
}

중복 조합은 같은 수를 뽑을 수 있고 순서가 존재한다 이에 같은수는 뽑을 수 있지만 순서가 다르고 동일한 요소로 이루어져있는 것은 이전에 뽑은것과 같음으로 허용치 않는다

이 정도 문법은 꼭 기억하도록 하자