algorithm Study/2014/koi_virus

Difference between r1.9 and the current

@@ -8,14 +8,14 @@

=== 아이디어 ===
* [http://183.106.113.109/30stair/KMP_doc/KMP_doc.php?pname=KMP_doc KMP Algorithm]
* KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.

* ~~Virus라면~~, 모든 모든 프로그램에 존재할 것이다. ~~Virus가~~ 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.

* 한 ~~Program에서~~ 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 ~~virus의~~ 후보가 된다.

* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, ~~프로그램에서~~ 제외한다.

* 바이러스라면, 모든 프로그램에 존재할 것이다. 바이러스가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.

* 한 프로그램에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 바이러스의 후보가 된다.

* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 후보에서 제외한다.

* 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES
* 시간 복잡도는 O(NM^2)
=== 풀다가 겪은 문제 ===
* KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.

* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함.

* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함. 도와준 이들 : joojis, bluemir

* 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.
* 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.
* 1차적으로 합으로 검색하고, 같으면 tuple까지 검색하자.

1. 문제

2. 권영기

2.1. 사용 언어
2.2. 아이디어
2.3. 풀다가 겪은 문제
2.4. 코드

1. 문제 ¶

http://183.106.113.109/pool/koi_virus/koi_virus.php?pname=koi_virus

2. 권영기 ¶

2.1. 사용 언어 ¶

2.2. 아이디어 ¶

KMP Algorithm
KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
바이러스라면, 모든 프로그램에 존재할 것이다. 바이러스가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.
한 프로그램에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 바이러스의 후보가 된다.
각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 후보에서 제외한다.
이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES
시간 복잡도는 O(NM^2)

2.3. 풀다가 겪은 문제 ¶

KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.
프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함. 도와준 이들 : joojis, bluemir
- 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.
- 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.
- 1차적으로 합으로 검색하고, 같으면 tuple까지 검색하자.
처음에는 Python으로 구현하였음. 근데 자꾸 시간 초과 나옴. 그러나 데이터 규모를 생각하면 시간초과가 나올만한 규모는 아님. 언어적 특성을 파악하지 못해서 생긴 결과물로 예상하고 있음. 한 시간은 날린듯
같은 아이디어로 C++로 구현하니까 시간 안에 잘 나옴. ㅠㅠ
Python으로 구현한 누군가는 5초안에 나오는데 어떻게 풀었는지 궁금함.

2.4. 코드 ¶

#include<iostream>
#include<memory.h>
using namespace std;
int n, k;
int pi[1020];
int program[120][1020];
int program_size[120];
int virus_candidate[2020][1020];
bool answer = true;
bool virus_check[2020];
int find_pi(int p){
	int i = 0, j = -1;
	pi[0] = -1;
	while(i < k){
		if(j == -1 || virus_candidate[p][i] == virus_candidate[p][j]){
			i++;
			j++;
			pi[i] = j;
		}
		else{
			j = pi[j];
		}
	}
        return 0;
}
bool kmp(int s, int p){
	int i = 0, j = -1;
	memset(pi, 0, sizeof(int) * 1020);
	find_pi(p);
	while(i < program_size[s]){
		if(j == -1 || program[s][i] == virus_candidate[p][j]){
			i++;
			j++;
		}
		else{
			j = pi[j];
		}
		if(j == k){
			return true;
			j = pi[j];
		}
	}
	return false;
}
int main(void)
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);

	cin>>n>>k;
	for(int i = 0; i<n; i++){
		cin>>program_size[i];
		for(int j = 0; j<program_size[i]; j++){
			cin>>program[i][j];
		}
	}
	int count = 0;
	for(int i = 0; i<program_size[0] - k + 2; i++){
		for(int j = 0; j<k; j++){
			virus_candidate[count][j] = program[0][i + j];
			virus_candidate[count + 1][j] = program[0][i + k - j - 1];
		}
		count += 2;
	}
	
	int m = count;
	for(int i = 1; i<n; i++){
		for(int j = 0; j<m; j+=2){
			if(!virus_check[j] && !kmp(i, j) && !kmp(i, j + 1)){
				virus_check[j] = virus_check[j+1] = true;
				count -= 2;
			}
		}
		if(count == 0){
			answer = false;
			break;
		}
	}

	if(answer)cout<<"YES";
	else cout<<"NO";

}