본문 바로가기

Algorithm/BOJ47

[boj] 11657 - 타임머신(shortest path, bellman-ford) www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 최단거리 문제이다. 간선의 가중치가 음수인 케이스가 있으므로 다익스트라 알고리즘으로 풀 수 없고, 벨만포드 알고리즘으로 풀어야 한다. 노드가 n개일 때, 최대 n-1개의 간선에 대하여 최단거리를 계산해준다. 따라서 시간복잡도는 n개의 노드에 대해서 n-1개의 간선을 검사하므로 O(V*E) = O(V^3)이 나온다. 다만 음수사이클이 있는 경우를 계산하.. 2021. 3. 29.
[boj] 8980 - 택배(greedy) www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net - 그리디 방식으로 접근했다. 출발지에서 도착지가 가까운 도시의 박스를 옮기는 것이 최적의 해를 구할 수 있다. - 도착지가 가까운 순으로 배송정보를 정렬하고, 트럭이 지나가는 마을마다 트럭이 상자를 실을 수 있는 최대치를 모두 더한다 - 경로상에서 트럭이 실을 수 있는 최대치는 (최대용량 - 이미 실고 있는 박스) 이다 #include #include #include using namesp.. 2021. 3. 29.
boj 1197 - 최소 스패닝 트리(MST, kruskal) www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net MST를 구할 때 사용하는 알고리즘은 프림, 크루스칼 알고리즘이 있다. (V, E)가 각각 그래프의 노드, 엣지의 갯수 일때 노드를 기준으로 MST를 찾아나가는 프림 알고리즘은 은 복잡도가 O(V*E) = O(V^3)이고, 엣지를 기준으로 Disjoint set을 합치면서 사이클이 생기지 않았는지 검사하는 union-find 알고리즘을 이용하면 복잡도가 O(Elog.. 2021. 3. 28.
1922- 네트워크 연결 C++(MST, prim or kruskal, BFS) www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리를 만드는 문제이다. MST를 구하는 알고리즘에는 프림, 크루스칼 알고리즘이 있는데, 그 중 정점을 기준으로 최소비용 엣지을 추가해나가며 MST를 만들어나가는 프림 알고리즘을 이용했다. 크루스칼 알고리즘은 간선을 기준으로 사이클이 만들어지는 지 여부를 union-find 알고리즘으로 파악해나가면서 최소비용 엣지을 MST에 추가해 나가는 알고리즘이다. priority_queue을 이용해서 특정 노드에서 갈 수 있는 엣지의 최소값을 찾아내고, bfs를 하면서 방문해나간다. 우선순위 큐를 .. 2021. 3. 28.

티스토리툴바