기록을

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

재귀로 트리 순회를 구현해주면 된다.

무조건 대문자로 들어온다고 했기 때문에 'A'를 빼주면서 A부터 0에 대응되도록 인덱스를 잡아준다.

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

이 문제를 무작정 n^2으로 풀면 TLE를 받는다.

아래는 시간초과가 나는 코드이다.

한 대각선에 비숍은 하나밖에 존재할 수 없다는 것을 이용하면 복잡도를 2n-1 즉 n으로 떨어트릴 수 있을 것이다.

#include<iostream>
using namespace std;
int n, m[10][10];
int cnt = 0, Max = 0;
bool isused1[10], isused2[10];
void func(int k) {
	
	if (Max < k) Max = k;

	bool isExist1 = false , isExist2 = false;
	for (int i = 0; i < 10; i++) {
		if (!isused1[i]) {
			isExist1 = true;
			break;
		}
		if (!isused2[i]) {
			isExist2 = true;
			break;
		}
	}

	if (!isExist1 && !isExist2) return;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (m[i][j] == 1 && !isused1[i + j] &&
				!isused2[i - j + n - 1]) {
				//cnt++;
				isused1[i + j] = true;
				isused2[i - j + n - 1] = true;
				func(k + 1);
				isused1[i + j] = false;
				isused2[i - j + n - 1] = false;
			}
		}
	}
	return;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	
	func(0);
	cout << Max << '\n';
}

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

C개의 수를 입력받아서 길이 L의 수열을 출력하면 된다.

입력은 소문자로만 들어오고, 정렬되어서 들어오지 않는다.

출력되는 수열은 오름차순 정렬 상태여야 하기 때문에 입력을 받은 이후에 정렬이 필요하다. 그리고 사전순의 상태를 유지하기 위해서 st라는 변수를 두어서 이전에 사용된 문자의 인덱스를 관리한다.

문자의 길이가 0이 되면 이 전에 사용한 문자의 인덱스가 존재하지 않기 때문에 0으로 처리해준다.

문자를 중복해서 사용할 수 없기 때문에 특정 인덱스의 문자가 사용중인지 여부를 판단하는 배열이 필요하다.

출력되는 문자열의 문자 사이사이에 공백이 당연히 포함된다고 생각해서 공백까지 출력해서 맞왜틀을 반복했다.

출력 형식을 잘 확인하도록 하자.

#include<iostream>
#include<algorithm>
using namespace std;
int L, C, st;
char n[15], arr[15];
bool isused[15];
bool Check() {
	int cntM = 0, cntJ = 0;
	for (int i = 0; i < L; i++) {
		if (arr[i] == 'a' or arr[i] == 'e' or
			arr[i] == 'i' or arr[i] == 'o' or arr[i] == 'u')
			cntM++;
		else
			cntJ++;
	}
	if (cntM >= 1 && cntJ >= 2) //모음1, 자음2개가 있어야 true
		return true;
	else
		return false;
}
void func(int k) {
	if (k == L) {
		if (Check()) {
			for (int i = 0; i < L; i++)
				cout << arr[i];
			cout << '\n';
		}
		return;
	}
	if (k == 0) st = 0;
	for (int i = st; i < C; i++) {
		if (!isused[i]) {
			arr[k] = n[i];
			isused[i] = true;
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> L >> C;
	for (int i = 0; i < C; i++)
		cin >> n[i];
	sort(n, n + C);
	
	func(0);
	return 0;
}

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

사용했던 숫자를 여러 번 사용할 수 있다.

따라서 숫자 사용 여부를 관리하는 배열이 필요하지 않다.

수열을 벡터에 쌓고, 원하는 길이만큼 쌓이면 set에 넣고 벡터를 비워주는 것을 반복한다.

set에는 중복되는 원소가 들어갈 수 없다는 것을 활용했다.

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, num[8], arr[8], Start;
set<vector<int> > st;
void func(int k) {
	if (k == m) {
		vector<int> v;
		for (int i = 0; i < m; i++)
			v.push_back(arr[i]);
		st.insert(v);
		v.clear();
		return;
	}
	if (k == 0) Start = 0;
	for (int i = Start; i < n; i++) {
		arr[k] = num[i];
		Start = i;
		func(k + 1);
	}

}
int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	func(0);
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

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

n개의 숫자중에 6개를 뽑아서 수열을 만들고, 오름차순 정렬하여 출력해주면 된다.

입력으로 들어오는 숫자는 정렬된다는 조건이 없다는 것을 주의해야 한다.

1. next_permutation 활용 구현

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[50], Sel[50];
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) return 0;
		
		for (int i = 0; i < n; i++)
			cin >> a[i];
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			if (i < 6) Sel[i] = 0;
			else Sel[i] = 1;
		}
		
		do {
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) cout << a[j] << ' ';
			}
			cout << '\n';
		} while (next_permutation(Sel, Sel + n));
		cout << '\n';
	}
	return 0;
}

2. 백트래킹 활용 구현

마찬가지로 사용할 수 있는 수들을 입력 받은 이후에, 수열을 오름차순으로 만들어내기 위해서 정렬을 수행한다.

조합이기 때문에 매 재귀마다 0부터 확인하는 것이 아니라 이전 재귀에서 사용했던 숫자의 위치를 파악해서 그 숫자 이후로 사용할 수 있는 숫자를 찾는다.

#include<iostream>
#include<algorithm>
using namespace std;
int n, num[50], arr[7];
bool isused[50];
int st;
void func(int k) {
	//여기서 수열의 길이 k
	if (k == 6) {
		for (int i = 0; i < k; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	if (k == 0) st = 0; //0일때 초기화
	for (int i = st; i < n; i++) { //조합으로 만들기 위해 st부터. 0부터 뽑으면 순열(순서가 다르면 다른 수열)
		if (!isused[i]) {
			isused[i] = true;
			arr[k] = num[i];
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		sort(num, num + n);
		func(0);
		cout << '\n';
	}
}

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

퀸은 놓여있는 위치의 행과 열 그리고 대각선 두 방향을 공격할 수 있다.

N이 15 정도밖에 되지 않기 때문에 백트래킹을 해도 충분하다.

먼저 행당 1개의 퀸이 있는 것은 당연하다.

따라서 우리는 특정 열에 퀸을 놓을 수 있는가, 특정 대각선에 퀸을 놓을 수 있는가를 관리해주면 된다.

#include<iostream>
using namespace std;
int n;
bool isused[3][40];
int cnt = 0;
void func(int k) {
	//k-1개 까지 다 놓은 상태
	if (k == n + 1) {
		cnt++;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (isused[0][i] || isused[1][k + i] || isused[2][k - i + n - 1])
			continue;
		isused[0][i] = true;
		isused[1][k + i] = true;
		isused[2][k - i + n - 1] = true;
		func(k + 1);
		isused[0][i] = false;
		isused[1][k + i] = false;
		isused[2][k - i + n - 1] = false;
	}
}
int main(void) {
	cin >> n;
	func(1);
	cout << cnt;
	return 0;
}

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

사용할 수 있는 숫자들 중에 중복되는 숫자가 있을 수 있다.

숫자는 중복해서 사용하면 안 되고 입력받은 개수만큼만 사용해야 하며

만들어낸 수열은 비내림차순이어야 한다.

#include<iostream>
#include<vector>
#include<unordered_set>
#include<set>
using namespace std;
int N, M, arr[9], n[9];
bool isused[9];
set<vector<int> > st;
vector<int> v;
void func(int k) {
	
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!isused[i] && arr[k - 1] <= n[i]) {
			isused[i] = true;
			arr[k] = n[i];
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> n[i];
	}
	func(1);
	for (set<vector<int> >::iterator it = st.begin(); it != st.end(); it++) {
		for (int i = 0; i < (*it).size(); i++) {
			cout << (*it)[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

쉽게 풀려면 쉽게 풀 수 있는 문제이다.

문제를 살펴보자. 먼저 같은 숫자가 여러 번 등장할 수 있다는 조건이 있다.

즉 1 9 9 이런식으로 숫자의 목록이 있다면, 길이 2의 수열이 19 19 91 99 91 99 이렇게 3p2개 나올 수 있다는 것이다.

이제 중복을 제거해줘야 하고, 오름차순으로 정렬을 해줘야 한다.

정렬 방법은, 지금까지 그래 왔던 것처럼 미리 사용 가능 숫자들을 정렬해주면 된다.

또한 중복을 제거할 때는, 여러가지 방법이 물론 있겠지만, 간단하게 중복을 허용하지 않는 set을 사용했다.

set에 어떤 data를 삽입할 때, 이미 같은 데이터가 set 내부에 존재하면, 삽입 시도는 무시된다.

그런데 이번 문제를 풀던 도중 새로운 사실을 알았다.

처음에는 string type으로 공백과 함께 set에 담아서 출력을 하려고 했다.

따라서 set<string> 이렇게 타입을 잡았는데, set 안에 들어가게 되면 string을 나중에 꺼내서 사용할 때 string의 길이가 1이 된다는 것이다. 즉 string이 내가 평소에 아는 string이 아니게 된다.

이 문제를 해결하기 위해 set안에 vector을 넣기로 하고 문제를 해결했다. vector는 이상 없이 작동했다.

#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int n, m, arr[11], num[11];
bool isused[11];
set<vector<int> > ctnr;
void func(int k) {
	if (k == m + 1) {
		vector<int> v;
		for (int i = 1; i <= m; i++) {
			v.push_back(arr[i]);
		}
		ctnr.insert(v);
		v.clear();
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (!isused[i]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);

	func(1);

	/*for (set<string>::iterator i = ctnr.begin(); i != ctnr.end(); i++) {
		for (int j = 0; j < (*i).length(); j++) {
			if (j % 2 == 0) cout << stoi((*i).substr(j, 1));
			else cout << ' ';
		}
		cout << '\n';
	}*/
	for (auto e : ctnr) {
		for (int i = 0; i < e.size(); i++) {
			cout << e[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

사용할 수 있는 수들을 오름차순 정렬한다.

이전 자리에서 사용한 숫자보다 다음에 사용할 자리의 숫자가 크거나 같으면 된다.

숫자를 중복해서 사용할 수 있으니, 숫자의 사용 여부를 관리하는 배열도 필요하지 않다.

#include<iostream>
#include<algorithm>
using namespace std;
int num[9], arr[9];
int n, m;
void func(int k) {
	if (k == m + 1) {
		for (int i = 1; i <= m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (arr[k - 1] > num[i]) continue; //k가 1이면 arr[] = 0 이라서 상관X
		else {
			arr[k] = num[i];
			func(k + 1);
		}
	}
}
int main(void) {
	
	cin >> n >> m;
	//n개 가지고 길이 m
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);
	func(1);
	return 0;
}

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

숫자를 중복해서 뽑을 수 있기 때문에 숫자의 사용 여부를 관리하는 배열이 필요가 없다.

num배열에 사용할 수 있는 수들을 입력받고 정렬해준다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[8], arr[8];

void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		arr[k] = num[i]; //k번째 자리로 i번째 숫자 선택
		func(k + 1); //k+1번째 자리 정하기
	}
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1); //수열이 오름차순으로 나오게 하기 위해 오름차순 정렬
	func(1); //1번째 자리를 선택할 차례

	return 0;
}