본문 바로가기

Hub Algorithm/플로이드 워셜 알고리즘

Hub Algorithm/플로이드 워셜 알고리즘 2024. 6. 11. [BOJ] 백준 2458 : 키 순서 (java) 🧪 2458 키 순서난이도 : 🌟 골드 4유형 : 플로이드-워셜 알고리즘https://www.acmicpc.net/problem/2458 📝 문제1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.1번 학생의 키 3번 학생의 키 5번 학생의 키 4번 학생의 키 4번 학생의 키 5번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학..
Hub Algorithm/플로이드 워셜 알고리즘 2024. 6. 2. [BOJ] 백준 2224 : 명제 증명 (java) 🧪 2224 명제 증명난이도 : 🌟 골드 4유형 : 플로이드-워셜https://www.acmicpc.net/problem/2224 📝 문제수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다. 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.어떤 참인 명제가 주어졌을 때, 이 명제가 참이므로 이 명제 자체도 증명될 수 있다고..
Hub Algorithm/플로이드 워셜 알고리즘 2024. 3. 14. [BOJ] 백준 1613 : 역사 (java) 🧪 1613 역사 난이도 : 🌟 골드 3 유형 : 플로이드 워셜 알고리즘 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 📝 문제 역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다. 세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자. 입력 첫째 ..
Hub Algorithm/플로이드 워셜 알고리즘 2024. 3. 13. [BOJ] 백준 11404 : 플로이드 (java) 🧪 11404 플로이드 난이도 : 🌟 골드 4 유형 : 플로이드 워셜 알고리즘 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 📝 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수..

티스토리툴바