https://www.acmicpc.net/problem/3671 7자리 자연수까지의 모든 소수를 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 미리 구하고 브루트 포스(Brute Force)로 만들 수 있는 모든 숫자를 만들어서 소수인지 확인한다. 에라토스테네스의 체는 O(NloglogN)에 1~N까지 모든 소수를 구하는 알고리즘이다. 최대 7자리이므로 10000000*log(log(10000000)) := 8450980+ 모든 경우에 대하여이므로 대략 1억번의 연산이 넘지 않음을 알 수 있기에 시간 내에 해결할 수 있음을 알 수 있다. 123456789101112131415161718192021222324252627282930313233343536#include #includ..
https://www.acmicpc.net/problem/1956 d[i][i]는 처음에 INF이므로 플로이드를 돌린 후 d[i][i]가 갱신이 되었다면 i에서 출발해서 어딘가를 돌아서 i로 다시 왔다는 의미이다. 즉, 사이클이 존재한다는 뜻이다. 갱신이 한번도 되지 않았다면 -1, 갱신이 되었다면 그 중 최소값을 출력해주면 된다. 12345678910111213141516171819202122#include #include #define INF 987654321using namespace std; int i,j,k,n,m,a,b,c,d[400][400],ans=INF; int main(){ scanf("%d %d",&n,&m); for(i=0;i
https://www.acmicpc.net/problem/1507 이미 최단 거리가 주어졌기 때문에 다시 최단 거리를 계산할 때 갱신이 발생한다면 모순이므로 -1을 출력한다. i->j 거리와 i->k->j 거리가 같다면 i->j 간선은 필요가 없으므로 제외시켜준다. 1234567891011121314151617181920212223242526272829303132#include int n,d[20][20],c[20][20],ans; int main(){ scanf("%d",&n); for(int i=0;i
https://www.acmicpc.net/problem/2357 최소값과 최대값 각각에 대하여 세그먼트 트리를 만들어 준다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include using namespace std; int n,m,a[100001],maxt[400000],mint[400000]; void max_init(int node,int start,int end){ if(start==end) maxt[node]=a[start]; else { max_init(node*2,start,(start+end)/2)..
https://www.acmicpc.net/problem/11780 플로이드 와샬(Floyd-Warshall) 알고리즘은 그래프의 모든 정점 사이의 최단 거리를 O(N^3)에 구하는 알고리즘이다. 다이나믹 프로그래밍으로 접근하여 특정 정점 사이에 모든 경유지에 대해서 최단 거리를 갱신하면서 테이블을 채워 나간다. 이 문제는 최단 거리 + 경로까지 구하는 문제이다. 다음의 정점을 나타내는 path를 두고 i->k->j 에서 매번 경유지가 갱신될 때마다 다음정점이 k로 바뀌므로 path[i][j]를 path[i][k]로 바꿔준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #inc..
https://www.acmicpc.net/problem/1197 집합 연산을 나타내는 유니온 파인드를 이용한 크루스칼 알고리즘으로 최소 스패닝 트리(Minimum Spanning Tree)를 구성한다. 그래프의 모든 간선을 저장하고 정렬한 다음 가중치가 작은것 부터 뽑는다. 간선의 양 끝 정점이 같은 집합인지 파인드 연산을 통해 확인하고 다른 집합이면 유니온 연산을 통해 같은 집합으로 합쳐주고 간선을 최소 스패닝 트리에 추가한다. 이 과정을 모든 정점이 같은 집합에 포함될 때 까지 반복하면 N-1개의 간선으로 구성된 최소 스패닝 트리가 완성된다. 1234567891011121314151617181920212223242526272829303132#include #include #include using ..
https://www.acmicpc.net/problem/2042 수를 변경하는 쿼리가 없다면 i~j까지의 합을 부분합 S[j]-S[i-1]를 이용하여 O(1)만에 해결할 수 있다. 그러나 수를 변경하는 쿼리가 있기에 위의 방식으로는 수를 변경할 때마다 앞의 모든 부분합을 갱신해줘야 하기에 O(N)이 걸린다. 쿼리수가 M이라고 했을 때 최악의 경우 모든 쿼리가 갱신하는 쿼리라면 O(NM)이 걸리므로 문제를 해결할 수 없다. 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree)를 이용하여 업데이트를 O(logN)만에 할 수 있다. 세그먼트 트리 이용 1234567891011121314151617181920212223242526272829303132333435#include #incl..