와일드 카드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 50 
using namespace std;

int cache[101][101]; // [w][s]의 대응 여부를 저장
// 1이면 대응, 0이면 미대응, -1이면 미검사 

vector<string> ans;
string W;

bool matchMemoized(int w, int s, string S) { 
	int& ret = cache[w][s];
	if (ret != -1) // 이미 구한 값이면 그대로 반환5
		return ret;

	// 아직 구한 값이 아니면 검사 시작
	while (w < W.size() && s < S.size() && (W[w] == '?' || W[w] == S[s])) {
		w++; s++; 
	}

	if (w == W.size())
		return s == S.size();

	if (W[w] == '*') {
		for (int skip = 0; s + skip <= S.size(); skip++) {
			if (matchMemoized(w + 1, s + skip, S) == 1) { // 다음 문자열을 비교하여 대응된 경우
				return ret = 1; // ret에 1을 대입 후 반환
			}
		}
		return ret = 0; // 미대응된 경우 0을 대입 후 반환
	}
	else if (W[w] == '?') {
		bool flag = true; 
		for (int c = 0; c < S.size(); c++) {
			if (w == c)
				continue;
			if (S[c] != W[c])
				flag = false; 
		}
		if (flag)
			ans.push_back(S);
	}
}

void solve(string W, int n, string files[MAX]) {
	for (int i = 0; i < n; i++) {
		// cache 배열 초기화
		for (int i = 0; i < MAX; i++) {
			memset(cache[i], -1, sizeof(int) * MAX);
		}

		if (matchMemoized(0, 0, files[i])) {
			ans.push_back(files[i]);
		} // pattern과 files[i]를 검사
	}
	
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> W; // 패턴 문자열
		int n; cin >> n;
		string files[MAX];

		for (int i = 0; i < n; i++) {
			cin >> files[i];
		}
		solve(W, n, files);

		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << endl;
		}
		ans.clear();
	}
	return 0; 
}

답안 통과가 안되는 이유는 ,, ?

블로그를 참고해서 코드 리팩토링을 하고 다시 넣어주었다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 50 
using namespace std;

int cache[101][101]; // [w][s]의 대응 여부를 저장
// 1이면 대응, 0이면 미대응, -1이면 미검사 

string W, S;

bool matchMemoized(int w, int s) { 
	int& ret = cache[w][s];
	if (ret != -1) // 이미 구한 값이면 그대로 반환5
		return ret;

	// 아직 구한 값이 아니면 검사 시작
	while (w < W.length() && s < S.length () && (W[w] == '?' || W[w] == S[s])) {
		return ret = matchMemoized(w + 1, s + 1);
	}

	if (w == W.length() && (s == S.length()))
		return ret = 1; 

	if (W[w] == '*') {
		if (matchMemoized(w + 1, s)|| (s < S.length() && matchMemoized(w, s + 1))) { // 다음 문자열을 비교하여 대응된 경우
			return ret = 1; // ret에 1을 대입 후 반환
		}
	}
	return ret = 0; // 미대응된 경우 0을 대입 후 반환
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int cases; cin >> cases;
	while (cases--) {
		vector<string> ans;
		cin >> W; // 패턴 문자열
		int n; cin >> n;

		for (int i = 0; i < n; i++) {
			cin >> S; 
			memset(cache, -1, sizeof(cache));
			if (matchMemoized(0, 0) == 1)
				ans.push_back(S);
		}

		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << endl;
		}
	}
	return 0; 
}

solve함수를 없애주었고, S를 전역으로 ans를 지역으로 하여 문제를 해결하였다.

여기서는 return ret = 0 구문을 if(W[w] == '*') 안에 넣어서 프로그램이 제대로 동작하지 않은 것이다.

합친 증가 수열

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cache[101][101];
int n, m;
vector<int> A, B;

// 합친 증가 부분 수열의 최대 길이를 반환
int lis (int i, int j) {
	int& ret = cache[i][j];
	if (ret != -1) return ret;

	int maxElement = max(A[i], B[j]);
	ret = 2;
	for (int ni = i + 1; ni < n; ni++) {
		if (maxElement < A[ni])
			ret = max(ret, lis(ni, j) + 1);
	}
	for (int nj = j + 1; nj < m; nj++) {
		if (maxElement < B[nj])
			ret = max(ret, lis(i, nj) + 1);
	}
	return ret; 
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			int temp; cin >> temp;
			A.push_back(temp);
		}
		for (int j = 0; j < m; j++) {
			int temp; cin >> temp;
			B.push_back(temp);
		}

		memset(cache, -1, sizeof(cache));
		cout << lis(0, 0) << endl;

		A.clear(); B.clear();
	}
}