1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 516ms 다익스트라 특정 노드에서 다른 노드까지의 최단 경로를 계산하는 문제로 다익스트라 알고리즘을 이용하였다. 다익스트라 알고리즘 : 하나의 출발점에서 다른 모든 출발지까지 최단 경로 계산 최단 경로 알고리즘은 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘을 의미한다. 다익스트라 알고리즘 다익스트라 알고리즘은 gangintheremark.tistory.com imp..
1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 구하는 문제로 크루스칼 알고리즘과 프림 알고리즘으로 구현해보았다. 크루스칼 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘 신장 트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이 gangintheremark.tistory.com ..
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 244ms 벨만 포드 알고리즘 특정 노드(1번 노드)에서 모든 노드로 가는 가장 빠른 시간을 순서대로 출력하는 문제로 최단 경로를 계산하는 문제이다. 그리고 이 문제에서는 가중치가 음수의 값을 가지므로 다익스트라가 아닌 벨만 포드 알고리즘으로 최단 경로를 계산한다. 음의 가중치 순환으로 시간을 무한히 오래 전으로 되돌릴 수 있으면 -1 출력해야 하므로 전체 간선을 확인하며 최단 거리 테이블 d 를 갱신한..
모든 간선의 비용이 양수일 때는 다익스트라 최단 경로 알고리즘을 사용하면 된다. 하지만 음수 간선이 포함된다면? 음수 간선이 있는 경우 음수 간선 순환이 없는 경우 음수 간선 순환이 있는 경우 벨만 포드 알고리즘은 음수 간선의 순환을 감지할 수 있으며 음의 간선이 포함된 상황에서 사용할 수 있다. 시간복잡도는O(VE)로 다익스트라 알고리즘에 비해 느리다. 동작과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. V-1번 반복 3-1. 전체 간선 E개를 하나씩 확인 3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 4. 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행 → 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재 다익스트라 vs..
알고리즘 클릭 시, 해당 페이지로 이동정점 중심 구현최단 경로: 두 노드 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘다익스트라 알고리즘 : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 O(ElogV)플로이드 워셜 알고리즘 : 모든 노드에서 다른 모든 노드의 최단 경로 O(V3)최소 신장 트리(MST): 최소한의 비용으로 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프프림 알고리즘 : 시작 노드에서 가까운 노드를 선택하여 트리 구성 ➜ 사이클 검사X O(V2)간선 중심 구현최단 경로벨만포드 알고리즘 : 음의 가중치를 허용최소 신장 트리(MST)크루스칼 알고리즘 : 최소 비용의 간선을 차례대로 대입하여 트리를 구성 ➜ 사이클 검사必 O(ElogE)간선의 개수가 적은 ..
17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 120ms DFS BFS 부분집합 이 문제는 두 개의 선거구로 나누는데 같은 선거구끼리는 서로 인접해야 한다. n개의 구역들을 2개의 선거구로 나누기 ➜ 부분집합 DFS 각각의 선거구 구역들끼리 서로 인접한지 확인 ➜ BFS 두 개의 선거구로 나누는 작업은 부분집합으로 한 선거구에는 반드시 하나의 구역이 포함되어야 한다. private static void divide(int idx) { if (idx == N) { a.clear(); b.clear(); for (int i = 0; ..
프림 알고리즘 최소 신장 트리(MST)를 찾기 위한 알고리즘이다. 프림 알고리즘은 주어진 그래프에서 시작 정점을 선택하고 해당 정점을 기준으로 MST를 구축해나가는 방식으로 동작한다. 1. 시작 정점을 우선순위 큐에 넣는다. (우선순위 큐는 가중치에 따라 오름차순 정렬되어야 함) 2. 우선순위 큐에서 노드 하나를 꺼내 MST에 포함되어 있는지 확인 2-1. 포함되어 있다면 무시. 다시 1번으로 2-2. 포함되어 있지 않다면 방문처리 후 해당 노드와 연결된 노드를 우선순위 큐에 추가 3. 2번 과정 반복 최소 신장 트리에 대해서는 크루스칼 알고리즘 참고! static class Edge implements Comparable { int v; int cost; public Edge(int v, int cos..
신장 트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 최소 신장 트리(MST) 최소한의 비용으로 구성되는 신장 트리를 찾아야 하는 경우 → 예를 들어 N개의 도시가 있을 때, 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결되도록 최소한의 비용으로 도로를 설치하는 경우 크루스칼 알고리즘 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘으로 간선을 중심으로 해결한다. 그리디 알고리즘으로 분류된다. 동작과정 1. 간선 데이터를 비용에 따라 오름차순 정렬 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 2-1. 사이클이 발생하지 않는 경우 최소 신..
서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조 서로 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 합집합 Union : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기 Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 Union-Find 자료구조라고 한다. 동작과정 0. 노드 개수 크기의 부모 테이블을 자신의 값을 갖도록 초기화 1. 합집합 Union 연산을 확인하여 서로 연결된 두 노드 A, B를 확인 A와 B의 루트 노드 A’, B’를 각각 찾는다 A’를 B’의 부모 노드로 설정한다 2. 모든 합집합 Union 연산을 처리할 때까지 1번 과정 반복 #예시 Union(1, 4) Union(2,..
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 728ms 다익스트라 방향 그래프가 주어지고 출발 노드에서 모든 노드로의 최단 경로를 구하는 문제로 최소힙을 이용한 다익스트라 알고리즘을 구현하면 된다. # 소스코드 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable { int index; int distance; public Node(int index..
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 368ms 플로이드 워셜 인접행렬 모든 노드에서 다른 모든 노드까지의 최단 비용을 찾는 문제로 노드의 범위(N≤100)가 작아 플로이드 워셜 알고리즘을 이용한다. 이 문제에서 주의해야 할 점은 입력값으로 중복된 출발도시와 도착도시가 들어올 수 있다는 점 갈 수 없는 곳은 0으로 출력해야 한다는 점 따라서 처음 입력을 받을 때, 출발노드에서 도착노드로 가는 비용이 더 작은 것을 이차원 테이블에 넣어줘야한다. 또한 모든 노드를 INF 로 초기화 후 구현하기 때문에 마..
