while (1): study();

문제 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다. - 1번 학생의 성적 < 5번 학생의 성적 - 3번 학생의 성적 < 4번 학생의 성적 - 4번 학생의 성적 < 2번 학생의 성적 - 4번 학생의 성적 < 6번 학생의 성적 - 5번 학생의 성적 < 2번 학생의 성적 - 5번 학생의 성적 < 4번 학생의 성적 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하세요. 입력 조건 - 첫째 줄에 학생들의 수 N(2

그래프의 최단경로를 구할 수 있는 알고리즘이다. 특히 '모든 노드에 대해서 최단거리를 구하고 싶을 때 사용'한다. (반면, 다익스트라 알고리즘은 특정 노드 하나의 최단거리를 구하는 것에 특화되어 있다). 기본적으로 주어진 그래프에 대해서 다음과 같은 점화식을 수행한다. DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 즉 주어진 그래프에 대해서 특정 원소를 지나서 도달할 수 있는 경우의 수들을 차례로 고려하며 업데이트하는 것이다. 이때 i, j, k에 대해서 모두 노드의 개수만큼 순회해야하기 때문에 플로이드-워셜 알고리즘의 시간복잡도는 (O(N^3))이다. 따라서 노드의 개수가 1000개만 되어도 사용할 수 없다. 정리해보자면 다음과 같다. 장점: 구현이 매우 간단하다. ..

출처: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 이용한 최단경로 문제는 나오기만 하면 정말 땡큐인 문제인 듯합니다. 이 문제 역시 그래프의 노드 개수가 100개 이하이므로, 플로이드-워셜 알고리즘을 사용하여 손쉽게 해결할 수 있습니다. 플로이드-워셜 알고리즘에 대한 조금 더 상세한 설명은 다음 링크를 참조바랍니다. 링크: https://jcy1996.tistory.com/24?category=958980 플로이드..