굳건하게

문제 : https://www.acmicpc.net/problem/1305

KMP 문자열처리

KMP 알고리즘을 이용해 들어온 문자열의 접두사와 접미사가 같은 최대 길이를 구합니다. 그러면, 임의의 광고에서 앞(접두사) 뒤(접미사) 로 공통된 부분의 최대 길이를 구할 수 있고, 나머지 부분은 공통되지않으므로 그냥 덧붙여서 광고를 표현할 수 밖에 없습니다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> getPartialMatch(string N) {
	int m = N.size();
	vector<int> pi(m, 0);
	int begin = 1, matched = 0;
	while (begin + matched < m) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

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

	int N;
	string L;
	cin >> N >> L;
	vector<int> pi = getPartialMatch(L);
	cout << N - pi[N - 1] << '\n';
	return 0;

}

문제 : https://www.acmicpc.net/problem/4354

문자열처리 KMP

KMP 알고리즘을 활용해 문자열 L 에서 반복되는 구간을 찾는 문제입니다.

문자열 L 이 임의의 문자열 T = "xxx" 가 n번 반복되서 만들어졌다고 가정합시다.

그럼 다음과 같은 사실이 무조건 성립합니다.

문자열 L 에서 접두사와 접미사가 같은 최대 길이 = | L | - | T | 

즉, 접두사와 접미사가 최대로 같은 부분은 아래 그림과 같습니다.

따라서, 문자열 L의 최대 접두사와 접미사의 길이를 KMP 알고리즘을 이용해  구하고,

| L | 에서 빼준다면 | T | 를 구할 수 있습니다.

이때, | T | 의 제곱꼴로 | L | 이 이루어졌다면,  | L | % | T | 가 0 이 성립해야합니다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> getPartialMatch(string N) {
	int m = N.size();
	vector<int> pi(m, 0);
	int begin = 1, matched = 0;
	while (begin + matched < m) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

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

	while (1) {
		string L;
		cin >> L;
		int N = L.length();
		if (L == ".") break;
		vector<int> pi = getPartialMatch(L);
		if (N % (N - pi[N - 1]) == 0)
			cout << N / (N - pi[N - 1]) << '\n';
		else {
			cout << 1 << '\n';
		}
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/9935

문자열 문자열처리

 처음에는 KMP알고리즘을 사용해서 A  문자열에서 B 문자열을 다 찾고, 그 후 B 문자열을 다 지워주고, 다시 갱신된 문자열 A에 대해서 KMP 알고리즘을 사용해서 B 문자열을 다 찾는 방식으로 진행했습니다. 하지만, 시간초과 문제에 직면했고, 스택으로 문제를 해결할 수 있다는 힌트를 얻어서 순회하는 방식으로 문제를 다시 접근했습니다. ( 스택을 쓰지는 않았습니다! )

● A 문자열을 앞에서부터 순회하며 새로운 정답 문자열 C에 A를 넣어주며, C의 끝에서 B 문자열을 마주하게 되면 B 문자열을 지워주는 방식으로 진행하면 O(A.length()) 만에 문제를 해결할 수 있습니다.

ex ) 

mirkovC4nizCC44

C4

정답 문자열 C에 mirkovC 순서로 차례대로 push한 후, 4가 추가되면 C 문자열의 끝에 C4가 존재하므로 C4를 erase해줍니다. 그러면 이제 정답 문자열은 mirkov가 됩니다. 그 후 nizC를 push 해주고 mirkovnizC 상태에서 C4 가 들어와서 erase가 진행됩니다. 그 후 4가 들어와 또 C4가 존재하므로 erase해줍니다.

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string A, B, result;
	cin >> A >> B;
	int n = A.size(), m = B.size();
	for (int i = 0; i < n; i++) {
		result.push_back(A[i]);
		// result의 끝과 B의 끝이 같고, result에서 B를 뺄 수도 있는 크기
		if (result.size() >= B.size() && result.back() == B.back()) {
			// result의 끝에 B가 걸려있는지 확인해보자.
			bool flag = true;
			for(int j= 0; j < m; j++)
				if (result[result.size() - m + j] != B[j]) {
					flag = false;
					break;
				}
			if (flag) // 폭탄제거해야됨
				result.erase(result.size() - m, m);
		}
	}
	if (result.size() == 0) cout << "FRULA";
	else cout << result;
	return 0;
}

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

백트레킹 완전탐색

● 비숍은 대각선으로 움직이므로  체스판에서 흰색칸 / 검은색칸 으로 나눴을 때, 흰색칸에 있는 비숍은 흰색칸에 있는 비숍들끼리만 영향을 끼치고, 검은색칸에 있는 비숍은 검은색칸에 있는 비숍들끼리만 영향을 끼친다. --> 검은색 칸 / 흰색 칸 으로 나눠서 백트레킹을 각각 진행해주면 복잡도를 줄일 수 있습니다.

● 우리는 체스판의 왼쪽 위(0, 0) 부터 오른쪽 아래(N -1, N -1) 으로 비숍을 세울 수 있으면 세우고, 아니면 넘어가면서 진행할 것이므로 현재 비숍을 세울 수 있는 칸(1) 이면 왼쪽 위 대각선과 오른쪽 위 대각선에 비숍이 있는지 없는지만 체크하고, 왼쪽 아래 / 오른쪽 아래는 아직 비숍을 세우지 않았으므로 체크하지 않아도 됩니다.

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

int N, map[10][10];
int ansW, ansB;

bool check(int r, int c) {
	int tempR = r, tempC = c;
	while (0 <= tempR && 0 <= tempC) {
		if (map[tempR][tempC] == 2)
			return false;
		tempR--, tempC--;
	}
	tempR = r, tempC = c;
	while (0 <= tempR && tempC < N) {
		if (map[tempR][tempC] == 2)
			return false;
		tempR--, tempC++;
	}
	return true;
}

void Backtracking(int r, int c, int count, bool flag) {
	if (c >= N) {
		r++;
		if (c % 2 == 0) c = 1;
		else c = 0;
	}
	if (r >= N) {
		if (flag) ansW = max(ansW, count);
		else ansB = max(ansB, count);
		return;
	}
	if (map[r][c] == 1 && check(r, c)) {
		map[r][c] = 2;
		Backtracking(r, c + 2, count + 1, flag);
		map[r][c] = 1;
	}
	Backtracking(r, c + 2, count , flag);
}


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

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
	Backtracking(0, 0, 0, 0);
	Backtracking(0, 1, 0, 1);
	cout << ansW + ansB << '\n';
	return 0;
}