Hello, There

https://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 벨만-포드 알고리즘을 활용하는 문제. 벨만-포드 알고리즘은 다익스트라처럼 최단거리와 관련된 알고리즘이지만 1. 음수 간선이 존재하는 그래프에서 활용하며 2. 음수 사이클이 존재하는 그래프인지 판별하기 위해 사용하는 알고리즘이다. N개의 노드가 있을 때, 최단 거리를 만들 수 있는 최대 선택 노드의 개수는 N -1개이다. 따라서 N -1회..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import java.io.*; import java.util.*; public class Main { //인접리스트 static ArrayList[] arr; //방문 배열 static boolean[] visit; //최소비용 배열 static int[] costArr; public static void main(String[] args) throws IOEx..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬을 활용하면 쉽게 해결할 수 있는 문제. 위상 정렬은 사이클이 없고 간선이 방향성을 갖는 그래프에서, 노드의 순서를 정렬하는 알고리즘이다. 위상 정렬은 진입 차수를 기준으로 진행된다. 진입 차수란 어떤 노드 A가 있을 때, 노드 A를 가리키는 (노드 A 방향으로 진행되는) 간선의 수를 말한다. 이 문제에서는 키가 작은 학생부터 키가 큰 학생 순으..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드 알고리즘을 활용하는 문제. 유니온 파인드는 union 연산과 find 연산으로 이루어져있다. 대표노드 : 노드의 인덱스와 노드의 값이 일치하는 노드. union(a, b) : a의 대표노드와 b의 대표노드를 연결한다. (더 작은 노드를 대표로 할 지, 큰 노드를 대표노드로 할지는 마음대로) find(a) : a의 대표노드를 찾고 경로를 압축한다...

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프를 판별하는 방법을 알아야 하는 문제이다. 이분 그래프를 판별하기 위한 방법은 다음과 같다. 한 노드에서 시작하여 전체 노드를 탐색하며 처음 방문한 노드들을 번갈아가며 서로 다른 집합으로 분류한다. 갔던 노드를 다시 방문한 하는 경우, 다시 방문한 노드가 이전 노드와 같은 집합이라면 해당 그래프는 이분 그래프가 될 수 없으므로 탐색을 종료한다. 위의 탐색을 모든 노드에서 출발하는 경우에..

https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 찾아야 하는 동생의 수 S, 수빈이의 위치 N이 주어지고 그 다음에 동생들의 위치가 주어진다. 수빈이는 현재 위치 N을 기준으로 한걸음마다 D만큼을 이동할 수 있다. 이 때, 모든 동생들을 찾을 수 있는 D를 구해야 한다. 동생들의 위치가 1, 7, 11일때, 수빈이의 위치 3과의 관계를 살펴보면, 각각 수빈이와의 거리는 (절댓값으로) 2 , 4, 8이다. 거리에 ..