언제나 처음처럼

[문제 링크]

KMP 알고리즘이 활용되는 문제가 정말 많은거 같다.

금고를 반시계방향으로 돌려서 맞추는 횟수는 shifts(a, b) 함수의 반환값을 통해 알 수 있다.

돌리기 전 문자열을 a, 반시계 방향으로 돌리고 난 후 문자열을 b라고 했을 때 shifts(a, b) 를 수행하면 a문자열과 같은 문자열을 뒤에 붙인 문자열이 만들어지는데 이 문자열에서 b의 위치를 KMP 알고리즘을 통해 빠르게 구할 수 있다.

이 때 구한 b의 위치가 곧 돌린 횟수가 되므로 결과값에 누적시킨다.

문제를 해결하기 위해선 반시계방향, 시계방향으로 번갈아가며 돌려야 한다.

a문자열을 시계방향으로 돌려서 b문자열을 만드는데 돌리는 횟수와 b문자열을 반시계방향으로 돌려서 a문자열을 만드는 횟수가 같기 때문에 이를 이용하여 매개변수의 순서를 바꾼 shifts(b, a) 를 수행하면 동일한 결과를 얻을 수 있다.

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

vector<int> getPartialMatch(const string& s)
{
	int len = s.size();
	vector<int> pi(len, 0);

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (s[begin + matched] == s[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 KMPsearch(const string& h, const string& s)
{
	int hLen = h.size(), sLen = s.size();
	int ret;
	vector<int> pi = getPartialMatch(s);

	int begin = 0, matched = 0;
	while (begin <= hLen - sLen)
	{
		if (matched < sLen && h[begin + matched] == s[matched])
		{
			matched++;

			if (matched == sLen)
			{
				ret = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return ret;
}

int shifts(const string& original, const string& target)
{
	return KMPsearch(original + original, target);
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		vector<string> s(N+1);
		for (int i = 0; i <= N; i++)
			cin >> s[i];

		int sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (i % 2 != 0)
				sum += shifts(s[i], s[i + 1]);
			else
				sum += shifts(s[i + 1], s[i]);
		}

		cout << sum << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

KMP 알고리즘을 알기 전에는 팰린드롬 만들기 문제를 엄청 비효율적으로 풀었던거 같은데, KMP알고리즘을 배우면서 부분문자열의 접두사와 접미사가 일치하는 최대 길이를 효율적으로 구할 수 있게 되었다.

문자열 S와 이를 뒤집은 'S 문자열을 가지고 S의 접미사이면서 'S의 접두사가 되는 구간의 최대 길이를 찾은 다음, 문자열 S의 시작부분 부터 접미사가 시작되는 부분 전까지의 길이를 S 뒤에 붙여주면 가장 짧은 팰린드롬이 완성된다.

완성한 팰린드롬의 길이를 출력하면 원하는 결과를 얻을 수 있다.

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

vector<int> getPartialMatch(string& rS)
{
	int len = rS.size();
	vector<int> pi(len, 0);

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (rS[begin + matched] == rS[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 KMPsearch(string& S)
{
	int len = S.size();
	string rS;

	for (int i = len - 1; i >= 0; i--)
		rS.push_back(S[i]);
	
	vector<int> pi = getPartialMatch(rS);

	int begin = 0, matched = 0, addLen = len;
	while (begin + matched < len)
	{
		if (matched < len && S[begin + matched] == rS[matched])
		{
			matched++;
			
			if (matched == len - begin)
			{
				addLen = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return len + addLen;
}

int main(void)
{
	int tc;
	cin >> tc;
	
	while (tc--)
	{
		string S;
		cin >> S;
		cout << KMPsearch(S) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

스택을 사용하면 쉽게 풀 수 있는 문제였다.

배열 기준으로 move[i] - 1 위치에서 인형을 뽑게 되고, 인형을 찾을 때 까지(배열 원소가 0이 아닌 지점) depth = 0 부터 (board.size()-1) 까지 탐색한다.

인형을 찾으면 탐색을 종료하고 인형을 바구니에 담는다. 이때 바구니의 가장 위에 있는 인형과 동일한 인형이라면 가장 위에 있는 인형을 제거하고 answer 값을 2 증가시킨다.

만약 depth == board.size() 라면 인형을 못찾은 것이므로 건너뛰도록 구현하였다.

#include <string>
#include <stack>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;
	stack<int> basket;

	for (int i = 0; i < moves.size(); i++)
	{
		int depth = 0;

		while (depth < board.size() && board[depth][moves[i] - 1] == 0)
			depth++;

		if (depth == board.size())
			continue;

		int pick = board[depth][moves[i] - 1];
		
		board[depth][moves[i] - 1] = 0;

		if (!basket.empty() && basket.top() == pick)
		{
			basket.pop();
			answer += 2;
		}
		else
			basket.push(pick);

	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

N과 M의 최대 길이가 20으로 완전탐색을 돌리면 무난히 풀 수 있는 문제였다.

하지만 풀이법을 떠올리기가 정말 어려웠던거 같다.

처음엔 key 배열을 회전시키는 함수와 상하좌우로 한칸씩 밀어내는 함수를 구현해서 풀려고 했는데 조금만 생각해봐도 무수한 반례가 존재하는 풀이였다.

key를 모든 경우에 대조하기 위한 다른사람의 풀이법을 참고하기 위해 찾아보다 좋은 풀이법을 발견하고 바로 구현할 수 있었다.

https://regularmember.tistory.com/186

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> rotate(const vector<vector<int>>& key)
{
	int len = key[0].size();
	vector<vector<int>> ret(len);

	for(int i=0; i<len; i++)
		for (int j = 0; j < len; j++)
			ret[i].push_back(key[len-1-j][i]);

	return ret;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	int M = key[0].size(), N = lock[0].size();
	int T = N + (M - 1) * 2;
	vector<vector<int>> total(T);
	
	int concave = 0;

	for(int i = 0; i < T; i++)
		for (int j = 0; j < T; j++)
		{
			if ((i >= M - 1 && j >= M - 1) && (i <= T - M && j <= T - M))
			{
				total[i].push_back(lock[i-(M-1)][j-(M-1)]);
				if (lock[i-(M-1)][j-(M-1)] == 0)
					concave++;
			}
			else
				total[i].push_back(2);

		}

	for (int i = 0; i < 4; i++)
	{
		for (int startY = 0; startY <= T - M; startY++)
		{
			for (int startX = 0; startX <= T - M; startX++)
			{
				bool check = true;
				int remain = concave;

				for (int keyY = 0; keyY < M; keyY++)
				{
					for (int keyX = 0; keyX < M; keyX++)
					{
						int keyVal = key[keyY][keyX];
						int totalVal = total[startY + keyY][startX + keyX];

						if (keyVal == totalVal)
						{
							check = false;
							break;
						}
						if (keyVal == 1 && totalVal == 0)
							remain--;
					}
					if (!check) break;
				}
				if (check && remain == 0)
					return true;
			}
		}

		key = rotate(key);
	}

	return false;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

스택의 대표적인 문제라고 볼 수 있는 괄호 체크와 분할정복이 섞인 문제였던거 같다.

입력으로 주어지는 문자열 p는 곧 문자열 u = p와 빈 문자열 v가 주어진 형태라고 볼 수 있다.

따라서 문제에서 요구하는 알고리즘대로 구현하면 된다.

먼저 문자열 p가 올바른 괄호 문자열인지 확인해야 한다.

만약 올바른 괄호 문자열이라면 그대로 출력해주면 되고, 올바른 괄호 문자열이 아닐 경우 p를 u와 v로 나눠야 하는데

문제에서 u는 더이상 쪼개질 수 없는 균형잡힌 문자열로 나눠야 한다고 나와있기 때문에 '(' 와 ')' 의 개수가 같아지는 지점을 기준으로 u와 v로 나누면 된다.

마지막으로 나눠진 u에 대해서 올바른 괄호 문자열인지 확인하고, 문제에서 시키는데로 문자열을 완성해주면 된다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

bool match(const string& p)
{
	stack<char> temp;

	for (int i = 0; i < p.length(); i++)
	{
		if (p[i] == ')')
		{
			if (temp.empty())
				return false;
			
			temp.pop();
		}
		else
			temp.push(p[i]);
	}
	if (!temp.empty())
		return false;

	return true;
}

string solution(string p) {
	string answer = "";
	
	bool check = match(p);

	if (check)
		return p;
	else
	{
		int uLen;
		stack<char> temp;

		for (uLen = 0; uLen < p.length(); uLen++)
		{
			if (!temp.empty() && temp.top() != p[uLen])
				temp.pop();
			else
				temp.push(p[uLen]);

			if (temp.empty())
				break;
		}
		uLen++;

		string u = p.substr(0, uLen);
		string v = p.substr(uLen);

		check = match(u);

		if (check)
			answer = u + solution(v);
		else
		{
			answer = '(' + solution(v) + ')';
			for (int i = 1; i < uLen - 1; i++)
			{
				if (u[i] == '(')
					answer.push_back(')');
				else
					answer.push_back('(');
			}
		}
	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

문자열의 길이가 최대 1000이므로 모든 경우에 대해 시도해보는 O(N^2) 알고리즘을 구현해도 무난히 통과할 수 있다.

입력받은 문자열을 압축하기 전 길이가 최댓값이기 때문에 answer를 압축하기 전 길이로 초기화해주었다.

그다음 2중 for문을 통해 문자열을 1 ~ (s.length() / 2) 개 단위로 잘랐을 때 만들어지는 압축 문자열 중 길이가 가장 짧은 값을 answer에 갱신해주면 정답을 얻을 수 있다.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
	int sLen = s.length();
	int answer = sLen;
	
	for (int i = 1; i <= sLen / 2; i++)
	{
		string temp;
		string idx = s.substr(0, i);
		int cnt = 1;
		int here;

		for(here = i; here + i <= sLen; here += i)
		{
			if (idx == s.substr(here, i))
				cnt++;
			else
			{
				if (cnt > 1)
					temp += to_string(cnt) + idx;
				else
					temp += idx;

				idx = s.substr(here, i);
				cnt = 1;
			}
		}

		if (cnt > 1)
			temp += to_string(cnt) + idx;
		else
			temp += idx;

		temp += s.substr(here);

		answer = answer < temp.length() ? answer : temp.length();
	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

입력받는 문자열 T, P의 최대 길이가 100만으로 굉장히 길기 때문에 O(NM) 알고리즘으로 풀 수 없다.

따라서 시간복잡도가 O(N+M)인 KMP-algorithm을 구현하여 풀었다.

추가로 공백을 포함하는 문자열을 입력받기 위해 cin 함수가 아닌 getline(cin, str) 함수를 사용하였다.

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

vector<int> getPartialMatch(const string& P)
{
	int Plen = P.length();
	vector<int> pi(Plen, 0);

	int begin = 1, matched = 0;
	while (begin + matched < Plen)
	{
		if (P[begin + matched] == P[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

vector<int> KMPsearch(const string& T, const string& P)
{
	int Tlen = T.length(), Plen = P.length();

	vector<int> pos;
	vector<int> pi = getPartialMatch(P);

	int begin = 0, matched = 0;
	while (begin <= Tlen - Plen)
	{
		if (T[begin + matched] == P[matched])
		{
			matched++;
			
			if (matched == Plen)
				pos.push_back(begin + 1);
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pos;
}

int main(void)
{
	string T, P;

	getline(cin, T);
	getline(cin, P);

	vector<int> result = KMPsearch(T, P);

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';

	return 0;
}

알고리즘 200일 프로젝트 - 137 day

[문제 링크]

알고리즘 문제해결 전략 책에 있는 예제인데 투포인터를 응용한 재미있는 문제였다.

메모리 제한이 64MB 이하이므로 최대 50,000,000인 N을 배열에 담을 수 없다.

따라서 외계 신호를 받을때마다 구간합에 누적하고 결과값을 갱신해야 한다. 그리고 큐에 누적시킨 외계 신호를 보관하고 있다가 구간합이 K보다 커지게 되면 구간합이 K보다 같거나 작아질 때까지 먼저 들어온 순서대로 빼준다.

구간합이 K와 같다면 신호와 일치한 것이므로 결과값을 1 증가시킨다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

const long long MOD = pow(2, 32);

class Signal
{
	long long num;

public:
	Signal() : num(1983) {}
	int next()
	{
		long long ret = num;
		
		num = (num * 214013 + 2531011) % MOD;
		
		return ret % 10000 + 1;
	}
};

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int K, N;
		cin >> K >> N;

		Signal signal;
		queue<int> range;
		int ret = 0, rangeSum = 0;

		for (int i = 0; i < N; i++)
		{
			int nextSignal = signal.next();
			rangeSum += nextSignal;
			range.push(nextSignal);

			while (rangeSum > K)
			{
				rangeSum -= range.front();
				range.pop();
			}

			if (rangeSum == K)
				ret++;
		}

		cout << ret << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 136 day