AlgorithmStudy/2014/koi virus - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:35Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 28:		Line 28:
	using namespace std;		using namespace std;
	int n, k;		int n, k;
	int pi[1020];		int pi[1020];
	int program[120][1020];		int program[120][1020];
	int program_size[120];		int program_size[120];
	int virus_candidate[2020][1020];		int virus_candidate[2020][1020];
	bool answer = true;		bool answer = true;
	bool virus_check[2020];		bool virus_check[2020];
	int find_pi(int p){		int find_pi(int p){
	int i = 0, j = -1;		int i = 0, j = -1;
	pi[0] = -1;		pi[0] = -1;
	while(i < k){		while(i < k){
	if(j == -1 \|\| virus_candidate[p][i] == virus_candidate[p][j]){		if(j == -1 \|\| virus_candidate[p][i] == virus_candidate[p][j]){
	i++;		i++;
	j++;		j++;
	pi[i] = j;		pi[i] = j;
	}		}
	else{		else{
	j = pi[j];		j = pi[j];
	}		}
	}		}
Line 53:		Line 53:
	memset(pi, 0, sizeof(int) * 1020);		memset(pi, 0, sizeof(int) * 1020);
	find_pi(p);		find_pi(p);
	while(i < program_size[s]){		while(i < program_size[s]){
	if(j == -1 \|\| program[s][i] == virus_candidate[p][j]){		if(j == -1 \|\| program[s][i] == virus_candidate[p][j]){
	i++;		i++;
	j++;		j++;
	}		}
	else{		else{
	j = pi[j];		j = pi[j];
	}		}
	if(j == k){		if(j == k){
	return true;		return true;
	j = pi[j];		j = pi[j];
	}		}
	}		}
Line 75:		Line 75:
	cin>>n>>k;		cin>>n>>k;
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	cin>>program_size[i];		cin>>program_size[i];
	for(int j = 0; j<program_size[i]; j++){		for(int j = 0; j<program_size[i]; j++){
	cin>>program[i][j];		cin>>program[i][j];
	}		}
	}		}
	int count = 0;		int count = 0;
	for(int i = 0; i<program_size[0] - k + 2; i++){		for(int i = 0; i<program_size[0] - k + 2; i++){
	for(int j = 0; j<k; j++){		for(int j = 0; j<k; j++){
	virus_candidate[count][j] = program[0][i + j];		virus_candidate[count][j] = program[0][i + j];
	virus_candidate[count + 1][j] = program[0][i + k - j - 1];		virus_candidate[count + 1][j] = program[0][i + k - j - 1];
	}		}
	count += 2;		count += 2;
Line 92:		Line 92:
	for(int i = 1; i<n; i++){		for(int i = 1; i<n; i++){
	for(int j = 0; j<m; j+=2){		for(int j = 0; j<m; j+=2){
	if(!virus_check[j] && !kmp(i, j) && !kmp(i, j + 1)){		if(!virus_check[j] && !kmp(i, j) && !kmp(i, j + 1)){
	virus_check[j] = virus_check[j+1] = true;		virus_check[j] = virus_check[j+1] = true;
	count -= 2;		count -= 2;
	}		}
Line 107:		Line 107:

	}		}

imported>trailblaze at 10:33, 25 February 2014

2014-02-25T10:33:09Z

← Older revision		Revision as of 10:33, 25 February 2014
Line 11:		Line 11:
	* 바이러스라면, 모든 프로그램에 존재할 것이다. 바이러스가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.		* 바이러스라면, 모든 프로그램에 존재할 것이다. 바이러스가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.
	* 한 프로그램에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 바이러스의 후보가 된다.		* 한 프로그램에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 바이러스의 후보가 된다.
	* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, ~~프로그램에서~~ 제외한다.		* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 후보에서 제외한다.
	* 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES		* 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES
	* 시간 복잡도는 O(NM^2)		* 시간 복잡도는 O(NM^2)

imported>trailblaze at 01:37, 25 February 2014

2014-02-25T01:37:45Z

← Older revision		Revision as of 01:37, 25 February 2014
Line 16:		Line 16:
	=== 풀다가 겪은 문제 ===		=== 풀다가 겪은 문제 ===
	* KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.		* KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.
	* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함. ~~Thanks to~~ : joojis, bluemir		* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함. 도와준 이들 : joojis, bluemir
	** 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.		** 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.
	** 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.		** 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.

imported>trailblaze at 01:37, 25 February 2014

2014-02-25T01:37:28Z

← Older revision		Revision as of 01:37, 25 February 2014
Line 16:		Line 16:
	=== 풀다가 겪은 문제 ===		=== 풀다가 겪은 문제 ===
	* KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.		* KOI 지역본선 5번 문제여서 엄청 쫄았음. 위의 아이디어까지 생각하는데 얼마 걸리지 않았으나, 1억 5000만번의 연산 규모와 최악의 경우 모든 프로그램이 같은 프로그램일 경우가 나오면 시간초과가 나올지 모른다는 걱정에 의해서 좀 더 시간을 줄일 수 있는 방법을 고민해봄.
	* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함.		* 프로그램을 합을 이용해서 압축하는 방법. 길이 K의 Sub-Pattern을 O(1)만에 검색할 수 있게 합을 이용해서 압축함. Thanks to : joojis, bluemir
	** 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.		** 문제점은 Pattern이 달라도 합이 같을 수 있음 : 따라서 제곱합으로 압축하기로 함.
	** 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.		** 제곱합 또한 숫자는 같으나 순서만 다른 경우를 파악하지 못하므로, (합, Pattern)의 tuple 단위로 저장하기로 함.

imported>trailblaze at 01:36, 25 February 2014

2014-02-25T01:36:44Z

← Older revision		Revision as of 01:36, 25 February 2014
Line 9:		Line 9:
	* [http://183.106.113.109/30stair/KMP_doc/KMP_doc.php?pname=KMP_doc KMP Algorithm]		* [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)가 나오는 것을 고려해보면 엄청나게 빠름.		* KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
	* ~~Virus라면~~, 모든 프로그램에 존재할 것이다. ~~Virus가~~ 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.		* 바이러스라면, 모든 프로그램에 존재할 것이다. 바이러스가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.
	* 한 ~~Program에서~~ 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 ~~virus의~~ 후보가 된다.		* 한 프로그램에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 바이러스의 후보가 된다.
	* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 프로그램에서 제외한다.		* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 프로그램에서 제외한다.
	* 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES		* 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES

imported>trailblaze at 01:36, 25 February 2014

2014-02-25T01:36:14Z

← Older revision		Revision as of 01:36, 25 February 2014
Line 9:		Line 9:
	* [http://183.106.113.109/30stair/KMP_doc/KMP_doc.php?pname=KMP_doc KMP Algorithm]		* [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)가 나오는 것을 고려해보면 엄청나게 빠름.		* KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
	* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.		* Virus라면, 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.
	* 한 Program에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 virus의 후보가 된다.		* 한 Program에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 virus의 후보가 된다.
	* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 프로그램에서 제외한다.		* 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 프로그램에서 제외한다.

imported>trailblaze at 01:35, 25 February 2014

2014-02-25T01:35:09Z

← Older revision		Revision as of 01:35, 25 February 2014
Line 7:		Line 7:
	* C++		* C++
	=== 아이디어 ===		=== 아이디어 ===
	[http://183.106.113.109/30stair/KMP_doc/KMP_doc.php?pname=KMP_doc KMP Algorithm]		* [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)가 나오는 것을 고려해보면 엄청나게 빠름.		* KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
	* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.		* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.

imported>trailblaze at 01:34, 25 February 2014

2014-02-25T01:34:55Z

← Older revision		Revision as of 01:34, 25 February 2014
Line 7:		Line 7:
	* C++		* C++
	=== 아이디어 ===		=== 아이디어 ===
	* [http://183.106.113.109/30stair/KMP_doc/KMP_doc.php?pname=KMP_doc KMP Algorithm]		[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)가 나오는 것을 고려해보면 엄청나게 빠름.		* KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
	* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.		* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.

imported>trailblaze at 01:34, 25 February 2014

2014-02-25T01:34:09Z

← Older revision		Revision as of 01:34, 25 February 2014
Line 7:		Line 7:
	* C++		* C++
	=== 아이디어 ===		=== 아이디어 ===
	* KMP Algorithm		* [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)가 나오는 것을 고려해보면 엄청나게 빠름.		* KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
	* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.		* Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.

imported>trailblaze at 01:29, 25 February 2014

2014-02-25T01:29:35Z

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