https://www.acmicpc.net/problem/1753 다익스트라 (Dijkstra) 알고리즘은 모든 간선의 가중치가 음수가 아닌 그래프에서 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 가중치가 모두 같다면 BFS로 최단거리를 구할 수 있다. 먼저 시작점으로 부터의 최단거리를 나타내는 dist 배열을 할당하고 INF로 초기화한다. 일단 시작점의 최단거리가 0임은 알 수 있다. 그 다음 우선순위 큐(최소힙)을 이용하여 지금까지 구한 정점까지의 거리 중 최소값을 빼면서 인접 정점들을 검사한다. dist 값이 갱신될 때마다 큐에 (지금까지 찾은 최단거리,정점)을 넣어준다. 이 과정을 반복하다보면 시작점으로부터 다른 모든 정점까지의 최단거리에 해당하는 간선들로 이루어진 스패닝 트..
https://www.acmicpc.net/problem/1463 1로 만드는 최소 연산 횟수는 1에서 N까지 만드는 최소 연산 횟수와 같다. 이를 d[i]이라 하면 이전에 올 수 있는 연산들 중 최소에 1을 더하면 된다. d[i]=min(d(i-1],d[i/3],d[i/2])+1 Top-Down 구현 123456789101112131415161718192021#include #include using namespace std; int n,d[1000001]; int go(int n){ if(n==1 || d[n]) return d[n]; d[n]=go(n-1)+1; if(n%3==0) d[n]=min(d[n],go(n/3)+1); if(n%2==0) d[n]=min(d[n],go(n/2)+1); ret..
https://www.acmicpc.net/problem/1003 f(n)을 호출할 때 f(0)과 f(1)이 각각 호출되는 횟수의 점화식은 d[n]=d[n-1]+d[n-2] 로 같다. 기저값만 1,0과 0,1으로 각각 다르므로 f(1)에 관한 d 배열값이 하나씩 밀려서 나타난다. 따라서 f(0)에 관한 값만 구하고 출력할때 d[n],d[n+1]을 출력해주면 된다. 1234567891011121314151617#include int t,n,d[42]; int main(){ d[0]=1; for(int i=2;i
https://www.acmicpc.net/problem/1431 정렬 기준에 따라 비교 함수를 만들어준다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include using namespace std; bool cmp(string &a,string &b){ int s1=a.size(),s2=b.size(); if(s1!=s2) return s1
https://www.acmicpc.net/problem/1305 길이가 N인 광고판이 있고 광고(문자열)가 광고판을 꽉 채우면서 반복되서 나타난다. 이 때 가능한 광고의 길이 중 가장 짧은 것을 찾는 문제이다. 광고가 반복해서 밀려나면서 뒤에서도 나타난다. 따라서 광고판에서 prefix와 suffix가 같을 때 길이의 최대값을 구하고 N에서 이를 빼주면 가장 짧은 광고의 길이이다. 이는 KMP에서 실패 함수의 정의이다. 123456789101112131415161718192021#include #include #include using namespace std; int main(){ int n; string s; cin>>n>>s; vector pi(n); pi[0]=0; for(int i=1,j=0;..
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[..