Difference between r1.3 and the current
@@ -4,6 +4,107 @@
== 권영기 ==
=== 사용 언어 ===
* C++
=== 아이디어 === * [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)가 나오는 것을 고려해보면 엄청나게 빠름.
* 바이러스라면, 모든 프로그램에 존재할 것이다. 바이러스가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.
* 한 프로그램에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 바이러스의 후보가 된다.
* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 후보에서 제외한다.
* 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES
* 시간 복잡도는 O(NM^2)
=== 풀다가 겪은 문제 === * KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.
* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함. 도와준 이들 : joojis, bluemir
* 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.
* 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.
* 1차적으로 합으로 검색하고, 같으면 tuple까지 검색하자.
* 처음에는 Python으로 구현하였음. 근데 자꾸 시간 초과 나옴. 그러나 데이터 규모를 생각하면 시간초과가 나올만한 규모는 아님. 언어적 특성을 파악하지 못해서 생긴 결과물로 예상하고 있음. 한 시간은 날린듯 :(
* 같은 아이디어로 C++로 구현하니까 시간 안에 잘 나옴. ㅠㅠ
* Python으로 구현한 누군가는 5초안에 나오는데 어떻게 풀었는지 궁금함.
=== 코드 ==={{{
#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";
}
}}}
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까지 검색하자.
- 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.
- 처음에는 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";
}
