https://www.acmicpc.net/problem/1701 어떤 문자열의 모든 부분 문자열은 모든 suffix의 prefix들이다. 이를 이용하여 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 모든 suffix의 pi 배열을 구해서 최대값을 구해주면 된다. 1234567891011121314151617181920212223242526#include #include #include using namespace std; int main(){ string str; cin>>str; int len=str.size(),ans=0; for(int k=0;kpi[i]?ans:pi[i]; } } cout
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
https://www.acmicpc.net/problem/10159 모든 정점에 대하여 플로이드를 돌리고 비교 관계를 확인한다. 두 정점에 대하여 앞쪽이 더 큰지, 뒤쪽이 더 큰지 둘다 알 수 없다면 비교 관계를 알 수 없다. 123456789101112131415161718#include int n,m,i,j,k,d[101][101]; int main(){ scanf("%d %d",&n,&m); while(m--) scanf("%d %d",&i,&j),d[i][j]|=1; for(k=1;k
https://www.acmicpc.net/problem/2702 유클리드 호제법(Euclidean Algorithm)을 이용하여 최소공배수와 최대공약수를 구해준다. 12345678910111213141516#include int gcd(int a,int b) { return b?gcd(b,a%b):a; } int main(){ int t,a,b,g; scanf("%d",&t); while(t--) { scanf("%d %d",&a,&b); g=gcd(a,b); printf("%d %d\n",a*b/g,g); } return 0;}Colored by Color Scriptercs
https://www.acmicpc.net/problem/1939 정답(최대 중량제한)의 범위를 이분 탐색으로 줄여나가면서 최종 정답을 찾는다. BFS를 이용하여 답으로 정한 중량제한으로 시작점에서 도착점으로 갈 수 있는지 확인한다. 갈 수 있다면 범위를 올리면서 최대치를 찾고 갈 수 없다면 범위를 내린다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std; vector a[100001];int n,m,u,v,w,s,e; bool bfs(int w){ queue q; vector vis..
https://www.acmicpc.net/problem/1941 C(25,7)=480700가지의 모든 경우를 만들고 BFS로 7명이 인접해 있고 S가 4명 이상인지 확인한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include using namespace std; char map[5][6];bool visit[5][5];int ans,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0}; bool bfs(int sx,int sy){ int cnt=0,s=0; bool check[5]..