알고리즘

문제 읽기🤔 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지..

정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘 동작 그리디 + 동적 계획법 방문하지 않은 노드 중에서 가장 비용이 작은 노드를 선택(Greedy) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신(DP) 초기의 Dijkstra 알고리즘 거리 테이블을 매번 탐색하는 순차 탐색 방식 최악의 경우 모든 노드들을 확인해야 함 → 이것을 V번 반복 시간복잡도 $$O(V^2)$$ 방문 여부를 체크할 배열 각 노드까지의 최소 비용을 저장할 배열 미 방문한 노드는 무한한 값으로 초기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..