백준

백준 1219번 자바 ☆

1. 문제 https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 2. 접근 방식 기본적인 접근 방식은 벨만포드를 이용해서 푼다. 하지만 음의 사이클이 아닌 양의 사이클이라는 점과 시작 노드가 사이클에 속한 노드일 경우 도착 노드 또한 사이클에 속한것으로 봐야한다. 마지막으로 가장 중요한 부분은 양수 사이클이 존재할 때 시작 -> 도착 노드의 경로에 사이클이 존재 하지 않을 경우에 대한 예외 처리이다. 첫 번째 방법은 벨만포드 기본적인 탐색 횟수인 ..

백준 1916번 자바

1. 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 접근 방식 다익스트라로 접근하면 된다. 전형적인 방식이라 크게 어려움은 없다. 3. 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays;..

백준 1753번 자바 ☆

1. 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 접근 방식 다익스트라 알고리즘을 활용한다. 최소, 최단 등 관련 문제는 BFS, 다익스트라, 플로이드 와샬등의 알고리즘으로 해결하는 것이 일반적이다. 가중치 개념이 없는 경우, 2차원 배열의 맵에서 최소,최단 거리를 구할때는 BFS를 가중치 개념이 있는 경우, 한 가지의 노드를 기준으로 다른 노드들의 최소,최단거리는 Dijkstra를 모든 노드..

백준 1948번 자바

1. 문제 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 2. 접근 방식 위상정렬로 접근한다. 단, 마지막 도시에 도착 후 역순으로 1분도 쉬지않고 달리는 도로를 찾아야한다. 3. 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import ja..

백준 1516번 자바

1. 문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 2. 접근 방식 위상 정렬을 이용해서 구현하면 된다. 다만 예제와 달리 5 10 -1 10 1 -1 4 1 -1 4 3 2 5 -1 8 3 -1 이런 입력이 주어질 경우 while 문내에서 출력하면 5번째 건물의 누적시간이 4번째 건물의 누적시간보다 먼저 출력되므로 따로 반복문을 돌려 출력해야한다. 3. 구현 import java.io.BufferedReader; import..

백준 2252번 자바

1. 문제 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 2. 접근 방식 위상 정렬이란? -> 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 구현은? 인접 리스트를 구현해 인접 노드를 담아주면서 +1 순회를 마친 다음엔 값이 0인(즉, 초기 진입 노드)노드를 선입선출 형태의 자료구조에 넣어 poll하며 값을 -1 3. 구현 import java.io.BufferedReader; import..