전체 글 썸네일형 리스트형 KMP KMP는 주어진 문자열의 부분 문자열 중에서 비교 문자열과 매칭이 되는지 확인하는 알고리즘으로, 문자열 검색 알고리즘 중 하나입니다. 완전탐색의 방식으로는 두 문자열의 처음부터 끝까지 비교했다면, KMP는 이미 아는 정보를 이용해서 덜(?) 비교 합니다. 구체적으로 어떻게 하는 것일까요? 실패함수라는 것을 이용합니다. 실패함수는 매칭에 실패했을 때, 비교를 생략할 수 있는 범위를 알려주는 함수입니다. 설명을 위해 백준 1786번 문제를 인용하겠습니다. T라는 문자열과, P라는 문자열이 다음과 같을 때, 첫번째 비교는 다음과 같습니다. 1 2 3 4 5 6 7 8 9 … T : [ A B C D A B C D A B D E ] | | | | | | X P : [ A B C D A B D ] 1 2 3 4 .. 더보기 공항,암호코드 1. 1G>>P; for(int i=0;in; if(Union(n)) ans++; else break; } cout 더보기 곱셈, 이분탐색 1.분할정복 문제 : a를 b번 곱했을 때 c로 나눈 나머지를 구하세요 해결 : b 를 2로 계속 나눠가면서 계산한다 #include using namespace std; using ll=long long; ll ans=1; ll c; ll recur (ll a,ll b){ if(b==1) return a%c; if(b%2==0) { ll x=recur(a%c,b/2); ans=x%c*x%c%c; } else { ll x=recur(a%c,b/2); ans=x%c*x%c*a%c%c; } return ans%c; } int main() { ll a,b; cin>>a>>b>>c; cout>a>>b; ll c; for(int i=0;i>arr[i]; ll s= *min_element(arr, arr + a),.. 더보기 2075 - N번째 큰 수 priority queue pq의 크기를 N으로 고정 크기가 N보다 커지면 pop 또는 c++에서 algorithm 헤더 파일의 nth_element(fist, nth,last) 를 이용할 수 있다. #include #include using namespace std; priority_queue pq; int N; int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N; int count=N,n; for(int i=0;iN) pq.pop(); } } cout 더보기 13251 조약돌 조합 X 조합을 이용하면 너무 큰 숫자가 발생한다 따라서 확률로 계산해야 된다. +) 뽑을 개수 K 보다 (같은 색깔의) 조약돌의 개수가 적으면 확률을 계산하지 않아도 된다 #include using namespace std; using ll=long long; double ans; int main() { int N,K; ll total=0; cin>>N; int arr[N]; for(int i=0;i>arr[i]; total+=arr[i]; } cin>>K; for(int i=0;i 더보기 01.19 15904번 #include #include #include using namespace std; string str; int main() { string ans; getline(cin,str); int n1, n2, n3, n4; n1 = str.find('U'); n2 = str.find('C',n1); //n1 부터 찾는다 n3 = str.find('P',n2); n4 = str.find('C',n3); if (n1 == -1 || n2 == -1 || n3 == -1 || n4 == -1) { cout 더보기 이전 1 ··· 5 6 7 8 다음
