https://www.acmicpc.net/problem/1786 문자열 S에서 패턴 P를 찾는다고 하자. 일반적인 방법으로는 S의 모든 인덱스에 P를 매칭 시켜보는 방법이 있다. 하지만 이 방법으로는 S의 길이를 N, P의 길이를 M이라고 할 때, O(NM)이 걸리게 된다. 하지만 KMP(Knuth-Morris-Pratt) 알고리즘을 이용하면 O(M+N)에 할 수 있다. 먼저, 패턴 P에 대하여 실패 함수 pi[i]를 정의하자. pi[i] = P의 i까지의 부분 문자열에서 prefix와 suffix가 같은 부분 문자열 중에서 가장 긴 것의 길이 (단, prefix가 i까지의 부분 문자열과 같으면 안된다). 실패 함수를 이용하여 문자열 S를 스캔하면서 비교하지 않아도 되는 부분을 효율적으로 건너 뛸 수 ..
https://www.acmicpc.net/problem/2698 D[N][K][L] = 길이가 N이고 인접한 비트의 개수가 K개이면서 마지막 비트가 L인 수열의 개수라고 정의하자. 마지막 부분의 이전 상태와의 비교를 통해 점화식을 유도한다. 1. 마지막 비트가 0인 경우 이전 비트가 무엇이든 인접한 비트의 개수에 영향을 주지 않는다.D[N][K][0]=D[N-1][K][0]+D[N-1][K][1] 2. 마지막 비트가 1인 경우 이전 비트가 1이면 인접한 비트의 개수가 하나 추가된다.D[N][K][1]=D[N-1][K][0]+D[N-1][K-1][1] 1234567891011121314151617181920212223#include int t,a,b,d[101][101][2]; int main(){ d[..
https://www.acmicpc.net/problem/2660 회원의 점수는 나머지 회원들까지 최단 거리의 최대값이다. 이 때 회원의 수가 최대 50명이므로 플로이드로 간편하게 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int n,i,j,k,d[51][51],p[51],minv=100; int main(){ scanf("%d",&n); for(i=1;i