문제 링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 문제 풀이 다익스트라 풀이 건물 중 두 개를 뽑는 조합을 구하고 다익스트라 알고리즘으로 최단 거리를 구한다. - N : 건물의 개수, 노드 수, 최대 100 - M : 도로의 개수, 간선 수, 최대 N * (N-1)/2 = 4950 - 100개의 건물 중 2개를 뽑는 조합 : 100C2 = 100 * 99 / 2! = 4950 - 다익스트라 알고리즘 시간 ..

문제 링크 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^3) - 플로이드 워셜 공식 활용하여 각 노드별 최단 경로는 구한다 floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j] i -> j로 바로가는 비용과 k 를 거쳐 가는 i -> k -> j 비용 중 작은 값을 구한다 경로 추적 - (1,1) ~ (N, N) 까지 경로 추적하는 부분에서 시작과 끝 ..

문제 링크 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 문제 풀이 - 플로이드 워셜 기본 문제 - 시간 복잡도 = 플로이드 워셜 수행 + 친구 별 방에 대한 최단 거리 합산 + 최소 비용 가지는 방 번호 구하기 = O(N^3) + (N^2) + (N) (최대 친구 수는 N 이하, N번 방) 절차 1) 각 노드별 다른 노드에 대한 최단 경로를 플로이드 워셜 알고리즘으로 구한다, 시간 복잡도 O(N^3) 2) 친구별 방에 대한 최단 거리 비용을..

문제 링크 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 풀이 1) 각 노드별로 다른 노드에 대한 최단 거리를 구한다 (양방향 관계, 플로이드 워셜 알고리즘 사용) - 이때 시간복잡도 O(N^3) 2) 각 노드별 최단 거리를 구한 후 그 중 최대값이, 해당 노드의 회장 점수가 된다 3) 회장 점수가 최소가 되는 번호를 구해서 출력한다 문제에서 아래 부분이 조금 이해가 안 되었는데 결론은 각 노드별 최단 거리를 구해라는 의미였다 각 회원의..