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..