굳건하게

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

DP LIS BinarySearch

 가장 긴 증가 부분 수열을 구하는 문제로 DP를 이용해 해결할 수 있는데, DP 배열을 BinarySearch를 이용해 채워야한다.

Dp[ x ] := 길이가 x 인 증가 부분 수열 중 가장 작은 마지막 값

ex )

[ 4 2 6 3 1 5 ] 에서 길이가 2인 증가 부분 수열은 4 - 6 / 4 - 5 / 2 - 6 / 2 - 3 / 2 - 5 / 3 - 5 / 1 - 5 처럼 여러가지가 있지만, 이 중 가장 작은 마지막 값은 3이므로 Dp[2] = 3 이 된다.

지금까지 우리가 구한 가장 긴 증가 수열의 길이가 longest 라고 한다면, 우리가 지금 보고 있는 i번 째 값이 Dp[longest] 보다 크다면, 지금까지 구한 longest 길이의 수열의 뒤에 i번 째 값을 이으면 되므로 Dp[longest + 1] 을 갱신할 수 있다. 아니라면, 현재 값을 Dp[ k - 1] < i번 째 값 <= Dp[ k ] 인 곳을 찾아서 갱신하면 된다.(지금까지 구한 부분 증가 수열 중에서 맨 뒤에 값을 이을 수 있는 곳) 이때, Binary Search를 이용해야 시간초과를 해결할 수 있다. 또, 초기값으로 Dp[0] = -INF 로 설정하면 더 간편하게 구할 수 있다.

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

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

	const int INF = 99999;
	int N;
	cin >> N;

	vector<int> v(N), dp(N + 1, INF);
	for (int i = 0; i < N; i++)
		cin >> v[i];

	// dp[i] := 길이가 i인 증가수열들 중에서 마지막 값 중 최소.
	dp[0] = -INF;
	dp[1] = v[0];
	int longest = 1;
	for (int cur : v) {
		if (dp[longest] < cur) {
			longest++;
			dp[longest] = cur;
		}
		else {
			vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), cur);
			*it = cur;
		}
	}
	int ans = 1;
	for (int i = 1; i <= N; i++)
		if (dp[i] != INF) ans = i;
	cout << ans << '\n';
	return 0;
}

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

다익스트라 그래프 그래프이론

 1번 노드에서 시작해서 N번 노드까지 가는 최단 거리를 찾는 문제인데, K개 만큼의 길을 이동 거리(cost)를 0으로 만들 수 있는 상황에서의 최단 거리를 찾는 문제입니다.

 출발 노드가 정해져있으므로 다익스트라 알고리즘을 이용하고 몇 개의 길을 cost를 0으로 만들었는지에 따라 최단거리가 달라지므로, dist배열을 2차원 배열로 다음과 같이 정의하면 된다.

●  dist[M][K] := K개 만큼의 길을 0으로 만들어서 1번 정점에서 시작해서 M번 정점까지 이동한 최단 거리.

주의할 점 : 최단 거리가 int 형 범위를 벗어난다.

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const long long INF = 10000000001;
int N, M, K;
long long dist[10001][21];
vector<pair<int, int>> map[10001];

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

	cin >> N >> M >> K;
	for (int i = 0, x, y, z; i < M; i++) {
		cin >> x >> y >> z;
		map[x].push_back({ y, z });
		map[y].push_back({ x, z });
	}
	memset(dist, INF, sizeof(dist));
	priority_queue<pair<long long, pair<int, int>>> pq;
	pq.push({ 0, { 0, 1 } });
	for (int i = 0; i <= K; i++)
		dist[1][i] = 0;

	while (!pq.empty()) {
		long long cost = -pq.top().first;
		int road = pq.top().second.first;
		int cur = pq.top().second.second;
		pq.pop();
		if (dist[cur][road] < cost) continue;
		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			long long nextDist = cost + map[cur][i].second;
			// 현재 정점
			if (nextDist < dist[next][road]) {
				dist[next][road] = nextDist;
				pq.push({ -nextDist, {road, next} });
			}
			// 포장하고 진행
			nextDist = cost;
			if (road < K && nextDist < dist[next][road + 1]) {
				dist[next][road + 1] = nextDist;
				pq.push({ -nextDist, {road + 1, next} });
			}
		}
	}
	cout << dist[N][K] << '\n';
	return 0;
}

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

DP Bitmasking 비트마스킹

● 최대 길이가 50인 N개의 정수들을 뽑는 경우는 N! 개가 존재한다. N이 최대 15이므로, N! 개를 모두 구하면 시간초과 발생 --> DP 로 문제를 접근

● DP[state][r] := 현재 어떤 정수들을 뽑았는지 state에 비트마스킹을 이용해 표시하고, r 은 K로 나눴을 때 나머지를 의미한다.

 즉, DP[state][r] := state 상태에서 K로 나눴을 때 나머지가 r인 경우의 수

DP 배열을 채우기 위해 다음과 같은 정의가 미리 필요하다.

● mul[i] := pow(10, i) % K 를 미리 다 저장해둔다. mod 연산이므로 쉽게 계산 가능

● integer[i] := ( N개의 정수 중 i번 째 정수 ) % K 를 mul[] 을 이용해 미리 계산해놓는다.

그럼 DP[ i ] [ j ] 는 다음과 같이 채울 수 있다.

 현재 상태 ( i ) 와 나머지 j 에 대해서 N개의 정수를 다 뒤에 붙여본다. 이때, 이미 현재 상태에서 뽑아서 사용한 정수는 붙여주지 않는다.

 따라서, N개의 정수 중 k 번 째 정수를 뽑았다고 가정하면, i & ( 1 << k ) == 0 이 성립하면 그 정수를 붙여주고, 아니면 이미 사용한 정수이므로 넘어간다.

 이때, 정수를 붙여준다는 것은 현재 상태에서의 나머지 j 를 k번 째 정수의 길이만큼 옆으로 밀어주고, k번 째 정수를 붙여주는 것이므로 j * 10^(k번 째 정수의 길이)를 해주면 되는데, 미리 계산해놓은 mul 배열을 이용해 연산해주고, 뒤에 k번 째 정수를 붙여주는 연산은 integer 배열을 이용하면 된다.

 예시를 통해 익혀보면 현재 "12345" 를 만들었고, "678" 을 붙여주는 연산을 생각해보면 "12345" * 1000 + "678" 을 생각하면 된다.

 이때, 정수론에 의해 ("12345" * 1000 + "678") mod K == ("12345" * 1000) mod K + "678" mod K 와 동일하고, 더 쪼개면 == ("12345" mod K) * (1000 mod K) + ("678" mod K) 로 분해할 수 있다. "12345" mod K 는 우리가 DP[i][j] 에서 j에 해당되는 값이고, (1000 mod K) 는 mul 배열에서 다 계산했고, ("678" mod K) 도 integer 배열에 미리 다 연산해놓았으므로 쉽게 계산할 수 있다.

피드백

 처음에 DP 배열 정의까지는 떠올렸으나, DP 배열 초기화 및 채우는 방법에서 굉장히 오래 헤맸다.

 DP[i][j] 에 그냥 1 ~ N 번 째 정수를 다 붙여본다고 생각하면 간단한데 너무 꼬아서 생각한 것 같다.

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

int N, K;
long long dp[1 << 15][100];
long long factorial[16];
int integer[15];
int mul[51];
string list[15];

long long gcd(long long a, long long b) {
	while (b) {
		long long r = a % b;
		a = b;
		b = r;
	}
	return a;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> list[i];
	cin >> K;

	for (int i = 0; i < N; i++)
		reverse(list[i].begin(), list[i].end());

	factorial[1] = 1;
	for (int i = 2; i <= 15; i++)
		factorial[i] = factorial[i - 1] * i;

	mul[0] = 1;
	for (int i = 1; i < 51; i++)
		mul[i] = (mul[i - 1] * 10) % K;

	for (int i = 0; i < N; i++) {
		int temp = 0;
		for (int j = 0; j < list[i].length(); j++) {
			temp += ((list[i][j] - '0') * mul[j]) % K;
			temp %= K;
		}
		integer[i] = temp;
	}

	// dp 배열을 채워보자.
	dp[0][0] = 1;
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < N; k++) { // k번 째 친구를 안쓴애들만 쓰자.
				if ((i & (1 << k)) == 0) { // 현재 상태랑 k 사용이랑 겹치는게 없음.
					// 현재 나머지가 j --> k번 째 수를 사용하면 나머지가 바뀜
					int next = j * mul[list[k].length()];
					next %= K;
					next += integer[k];
					next %= K;
					dp[i | (1 << k)][next] += dp[i][j];
				}
			}
		}
	}

	long long g = gcd(dp[(1 << N) - 1][0], factorial[N]);
	cout << (dp[(1 << N) - 1][0] / g) << '/' << (factorial[N] / g) << '\n';

	return 0;
}

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

KMP 문자열 문자열찾기

 N개의 프로그램에서 K개 이상의 공통된 부분 수열을 찾는 문제로 K개의 공통된 부분 수열을 찾으면 되는 문제 입니다.

● 첫 번째 프로그램의 코드에서 K개 씩 가능한 모든 경우의 수를 뽑고, 나머지 프로그램에서 KMP 알고리즘을 이용해서 공통된 부분 수열이 있는지 없는지 찾으면 됩니다.

● 이때, J번 째 프로그램에서 KMP 알고리즘을 이용해 찾아보고, revserse 함수를 이용해 J번 째 프로그램의 코드를 뒤집은 뒤 KMP 알고리즘을 한 번 더 이용해 찾아봐야한다.

예시

K = 4

-1번 프로그램 { 10 8 23 93 21 42 52 22 13 1 2 3 4 }

-2번 프로그램 { 1 3 8 9 21 42 52 22 13 41 42 }

-3번 프로그램 { 9 21 42 52 13 22 52 42 12 21 }

1) 1번 프로그램에서 { 10 8 23 93 } 을 가지고 와서 2, 3번 프로그램에 KMP 진행

2) 1번 프로그램에서 { 8 23 93 21 } 을 가지고 와서 2, 3번 프로그램에 KMP 진행

같은 과정을 반복합니다.

6) 1번 프로그램에서 {42 52 22 13 } 을 가지고 와서 2, 3번 프로그램에서 KMP 진행

--> 2번 프로그램에서는 { 42 52 22 13 } 를 찾을 수 있고, 3번 프로그램에서는 revsere를 진행한 후에 { 42 52 22 13 } 을 찾을 수 있다. 

#include<iostream>
#include<vector>

using namespace std;

vector<int> getPartialMatch(vector<int> 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;
}

bool kmp(vector<int> H, vector<int> N) {
	int n = H.size(), m = N.size();
	vector<int> ans;
	vector<int> pi = getPartialMatch(N);
	int begin = 0, matched = 0;
	while (begin + m <= n) {
		if (matched < m && H[begin + matched] == N[matched]) {
			matched++;
			if (matched == m) // 끝까지 다 일치했습니다.
				return true;
		}
		else {
			if (matched == 0) begin++; // 일치한 부분이 하나도 없음 -> 시작포인트를 한 칸 앞으로
			else {
				begin += matched - pi[matched - 1]; // pi 배열을 이용해 다음 시작 지점으로 점프
				matched = pi[matched - 1]; // pi 배열을 이용해 이미 일치하는 부분을 건너뛰고 탐색 시작
			}
		}
	}
	return false;
}

int main(void) {
	int N, K;
	int length[100];
	vector<int> programs[100];
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> length[i];
		vector<int> t(length[i]);
		for (int j = 0; j < length[i]; j++) {
			cin >> t[j];
			programs[i] = t;
		}
	}
	bool ans = false;
	for (int i = 0; i < length[0] - K + 1; i++) {
		vector<int> n(K);
		for (int j = 0; j < K; j++)
			n[j] = programs[0][i + j];
		bool checked[100] = {};
		for (int j = 1; j < N; j++)
			checked[j] = kmp(programs[j], n);
		for (int j = 1; j < N; j++) {
			if (checked[j]) continue; 
			reverse(programs[j].begin(), programs[j].end());
			checked[j] = kmp(programs[j], n);
		}

		bool isVirused = true;
		for (int j = 1; j < N; j++)
			if (checked[j] == false) {
				isVirused = false;
				break;
			}
		if (isVirused) {
			ans = true;
			break;
		}
	}
	if (ans) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}