본문 바로가기
반응형

Algorithm-Java12

백준 - 11404 플로이드 - Java + 플로이드 워셜 백준 플로이드 문제를 풀어보았다. 이번 문제에서는 노드의 수가 100개로 적은 수이고, 모든 노드를 시작점으로 했을 때 최소 경로를 모두 출력하기 때문에 플로이드 워셜 알고리즘을 이용해 풀면 간단하게 풀 수 있는 문제이다. 추가로, 다익스트라를 각 노드를 시작점으로 실행하여 돌면 같은 결과이며 차이가 얼마나 나는지 궁금해 테스트해보았다 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 설명 n개 도시가 있고, 한 도시에서 출발하여 다른 도시.. 2023. 3. 27.
백준 - 11657 타임머신 -Java + 벨만-포드 백준 타임머신 문제를 풀어보았다. 이번 문제에서는 음수 가중치가 포함되며, 음수 사이클이 존재하는지도 판단해야 하는 문제로 다익스트라 알고리즘을 적용하지 못하고 벨만-포드 알고리즘을 적용해 보는 가장 기초적인 문제이다. 문제를 풀고, 벨만-포드 알고리즘에 대해서도 정리한다. 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 문제 설명 한 도시에서 출발하여 다른 도시에 도착하는 버스가 있.. 2023. 3. 26.
백준 - 1753 최단경로 - Java + 다익스트라 백준 최단경로 문제를 풀어보았다. 최단 경로는 대표적인 3가지 알고리즘이 있는데, 뭔가 어려워 보여서 계속 미루고 있었는데, 이번 기회에 공부해보았고 알아두면 유용하며 생각보다 어렵지 않은 알고리즘이었다. 세 가지 알고리즘에 대해서 곧 바로 문제에 적용해보면서 정리할 것이고, 이번 문제는 다익스트라를 적용하는 문제이다. 최단경로 풀이 알고리즘 다익스트라 벨만-포드 플로이드 워셜 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.a.. 2023. 3. 26.
백준 - 1477 휴게소 세우기 - Java 백준 휴게소 세우기 문제를 풀어보았다. 이분탐색과 비슷하지만 조금 다른 파라매트릭 서치라는 것을 배울 수 있어 정리한다. https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 풀이 시간: 40분 문제 설명 고속도로에 기존 휴게소가 있고, 휴게소 간 거리를 줄이기 위해 휴게소를 더 세운다 더 세우려는 휴게소의 개수 m개를 세웠을 때 휴게소 간 거리의 최댓값이 최소가 되도록 세우자 제한사항을 보면 크게 문제될 것으로 보이지 않고, 휴게소의 위치 범위만 생각 문제 풀이 예제를 .. 2023. 3. 24.
반응형

티스토리툴바