반응형 백준4 백준 - 11404 플로이드 - Java + 플로이드 워셜 백준 플로이드 문제를 풀어보았다. 이번 문제에서는 노드의 수가 100개로 적은 수이고, 모든 노드를 시작점으로 했을 때 최소 경로를 모두 출력하기 때문에 플로이드 워셜 알고리즘을 이용해 풀면 간단하게 풀 수 있는 문제이다. 추가로, 다익스트라를 각 노드를 시작점으로 실행하여 돌면 같은 결과이며 차이가 얼마나 나는지 궁금해 테스트해보았다 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 설명 n개 도시가 있고, 한 도시에서 출발하여 다른 도시.. 2023. 3. 27. 백준 - 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. 백준 - 12865 평범한 배낭 - Java 백준 평범한 배낭 문제를 풀어보았다. 기본 문제라곤 하지만 처음 풀다 보니 풀이를 기억해둬야 할 것 같아 정리한다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 시간: 1시간 문제 설명 준서가 여행을 가기 전 N개의 물건을 배낭에 담아 갈 생각이다. 각 물건은 무게 W, 가치 V를 가지며 버틸 수 있는 무게 K에 가치 V가 최대가 되게 꽉꽉 담으면 된다. 물건의 개수가 .. 2023. 3. 24. 이전 1 다음 반응형
