알고리즘77 [알고리즘] 파티 (백준 1238번) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 최단 시간만에 X번까지 왕복하는 시간을 구해야한다. 즉 각 마을에서 X번까지의 최단 시간, X번에서 각 마을까지의 최단 시간을 둘 다 구해야한다. 가장 쉽게 생각할 수 있는 방법은 플로이드 와샬로 모든 구간의 최단 시간을 구하는 것이다. 시간이 오래 걸리지만 풀긴 풀 수 있는 것 같다. (사실 1000의 3제곱이면 10억인데 못 풀 거라 생각했는데 풀긴 풀더라...) 하지만 X번까지의 왕복 정보 외에는 다른 정보들은 필요가 없다... 2020. 10. 7. [알고리즘] 숨바꼭질 3 (백준 13549번) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 처음엔 BFS인 줄 알았는데 자세히 보니 이동하는 위치에 따라서 이동시간이 다르다. 이 말은 곧 간선마다의 가중치가 다르다는 뜻이므로 다익스트라를 이용해야 한다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java... 2020. 10. 7. [알고리즘] ABCDE (백준 13023번) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 형태를 보면 알겠지만 DFS를 활용해서 depth를 파악해야하는 문제다. 처음엔 모든 노드들을 각각 시작점으로 하여서 한 번씩 DFS를 돌리려고 했는데 어째서인지 틀렸다고 나왔다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* import kotlin.collections.ArrayList var br = BufferedReader(In.. 2020. 10. 6. [알고리즘] 순열 사이클 (백준 10451번) 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net DFS를 이용하여 그래프의 사이클을 찾는 문제다. 사이클 찾는 문제는 꽤 자주 나오지만 막상 풀려고 하면 헷갈린다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* .. 2020. 10. 6. 이전 1 2 3 4 5 6 7 ··· 20 다음
