keicoon15

https://www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net Rabin-Karp Set을 사용해서 접근했음. 시간초과;; 구현이 잘못된건가ㅜ typedef struct{ char pattern[101]; int length; int h; int p; int dp; } rk; rk S[1001]; int d = 25, q = 101; int N, Q; void gHash(int index) { S[index].length = strlen(S[index..

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 제곱수의 개수를 찾아내어 전체 수에서 빼주면 된다. 단, 제곱수의 개수를 찾는것은 전체 범위의 min, max의 제곱근의 범위로 찾을 수 있다. 문제는 왜 틀렸는지 모르겠다ㅜ #define INT64 long long int main() { INT64 min, max; scanf("%llu %llu", &min, &max); INT64 A = (sqrtl(max) >= (INT64..

https://www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 특정 수열을 오름차순으로 만드는 또 다른 수열을 구하는 문제이다. 가장 쉽게 생각할 수 있는 방법은 현재 수열에서 가장 작은 숫자를 순차적으로 뽑아내어 해당 인덱스를 배열로 만들면 풀 수 있다. 단, 쉬운만큼 시간은 O(n^2)가 걸리므로 조금 더 어려운 조건일 경우 시간을 줄이는 방법을 새로 생각해야한다. #define MAXIMUM 1001..

https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문제 자체가 오토마타를 타겟으로 만든 문제같다. 여러 생각을 해봤지만 진짜 오토마타처럼 순서도를 작성해서 풀어봤다. 중간에 특정 조건이 존재하므로 잘 예외처리를 해야한다. 1. 10011001 (O) 2. 1001001 (X) 3. 100101 (O) typedef struct{ int next_state[2]; }state; state OM[7]; void makeSTATE(int i..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 특정 배추를 선택할 때 인접 배추들도 검색을 해야한다. 쉽게 생각하면 지뢰찾기에서 연쇄처리와 같다고 볼 수 있다. Queue에 현재 위치를 넣고 계속해서 주변에 만족하는 배추들의 위치를 추가한다. 이런식으로 모든 배추를 검색하면 DFS가 된다. 또 다른 예로는 퍼즐버블게임이나 뿌요뿌요같은 퍼즐게임에서 연쇄처리를 할 때 사용할 수 있겠다. using namespace std; bool MAP[50][50]; t..

https://www.acmicpc.net/problem/9987 9987번: 포켓몬 마스터 입력으로 포켓몬의 번호가 주어졌을 때, 그 포켓몬의 이름과 타입을 출력하는 프로그램을 작성하시오. www.acmicpc.net acmicpc 문제상 다른의미로 가장 힘들었다. 특정 사이트의 text를 긁어다 파싱하고 푸는 문제인데 중간중간 유니코드와 데이터를 잘 못 긁어올 경우 틀리기 쉽다. using namespace std; string poke[720]; int main() { poke[1] = "Bulbasaur\nGrass Poison"; poke[2] = "Ivysaur\nGrass Poison"; poke[3] = "Venusaur\nGrass Poison"; poke[4] = "Charmander\..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 0;i--,j--) { returnValue *= (double)i/(double)j; } return returnValue; } int main()..

https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a MAP; int g(int w, int a) { return (w*a)%10; } void makeMAP() { for(int i=0;i0;T--) { int a, b; scanf("%d %d", &a,..

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 문제에서 주어진 원 공간은 인접한 방의 개수가 항상 3개이다. 인접한 방은 항상 방의 숫자가 똑같으므로 인접한 방을 접근할 수 있는 자료구조를 만들고 데이터를 넣은 다음에 입력값(N)을 넘지않는 인접 방의 개수를 구하도록 저장했다. 자신의 인접한 방 중에 조건에 만족하는 방의 개수가 가장 적은 방부터 접근하여 풀어봤는데 결과는 실패이다. using na..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 무작정 계산하는 방식으로는 시간초과로 해결할 수 없다. DP를 사용하여 중간값들을 배열에 저장하여 해결할 수 있었다. typedef struct { int back[1001]; int back_num; }NODE; NODE MAP[1001]; int TIME[1001]; int ORDER[1001]; void input(int src, int des) { MAP[des].back[MAP[de..