My life story

1. 문제 링크 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 문제 개요 간선이 주어지고 출발지, 도착지의 정점 번호가 주어질 때, 출발지, 도착지까지의 최단거리, 경로를 구하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 인접 리스트로 나타낼 것. -> 한 정점에서 다른 정점까지의 간선이 1개라면 행렬로 나타내어도 괜찮다. 그런데 한 정점에서 다른 정점까지 간선이 여러 개 있을 수 있으니 인접 리스트로 나타내어야 한..

1. 문제 링크 www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 2. 문제 개요 주어진 도로의 거의 최단경로를 구하자. 거의 최단경로는 최단경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 3. 문제 힌트 최단경로를 제거해야 하기 때문에, dijkstra 최단경로 알고리즘을 1회 실행하자. 이때, O(n^2)가 아닌 log형태인 우선순위 큐를 사용해야 함. (시간 ..

1. 문제 링크 www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 2. 문제 개요 M원 이하로 사용하면서 도착지까지 갈 수 있는 최단 경로를 찾는 문제. 1원이든, M원이든 M원 이내에만 들면 되고 그중에서 최단 시간으로 갈 수 있는 경로를 찾자. 3. 문제 힌트 DP를 사용해야 한다. 경로를 찾을 때는 다익스트라 알고리즘(logn)으로 구현해서 사용해야 한다. 어떻게 DP를 적용할까? 점화식을 찾기에 앞서 왜 DP를 써야..

1. 문제 링크 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 2. 문제 개요 N개의 컴퓨터로 구성된 네트워크가 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다. 어느 날 해커가 침입해서 네트워크를 복구해야 하는 상황에 이르렀다. 다음 두 가지 조건을 만족해야 한다. (1). 최소 개수의 회선만을 복구해야 한다. 네트워크를 복구한 후에..