나의블로그

문제 링크 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 아이디어 그래프를 만들것이다. 문제를 해석해보면 1. a -> b 간선이 있을 때 a >= b 라면 간선을 추가 안해도 된다. 2. a->b 간선이 여러개 있을때 이중 가중치가 최대인 간선만 취해도 된다. 이런 그래프를 만들 것이고 1번에 의해 사이클이 없는 그래프 란걸 알 수 있다. (a < b, b < c인데 c < a일..

문제 링크 https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 아이디어 N이 1000이다. 따라서 floyd가 아닌 다익스트라를 쓰는건 확실하다. 세금이 인상될때 마다 다익스트라를 쓴다면? pq를 쓰는 다익스트라를 쓴다고 해도 O(K * (M + N)logN)은 썩 좋아 보이지 않는다. 다른 풀이가 필요하다. 우선 세금이 없는 경우 S->D의 특정 경로의 통행료를 A라하자. ..

문제 링크 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 아이디어 시간복잡도를 신경쓰지말고 생각해보자. 지금까지 입력받은 수들을 저장하는 리스트 arr이 있고, i(1 back[0]: tmp = -heappop(forward) heappush(back, tmp) while len(back) > i // 2 + 1: tmp = heappop(back) heappush(forward, -tmp) while len(back) < i..

목적 방향그래프에서의 사이클들을 찾는다. 우리가 구할것은 사이클관계인 정점들의 집합(리스트)이 원소인 리스트이다. (노드 1개도 하나의 사이클이 된다.) 사이클의 정의 방향그래프에서 a,b가 그래프에 포함되는 정점이라 하면 a -> b로가는 경로가 있고 b -> a로 가는 경로가 있는 경우이다. X를 정점 집합이라 할때 a -> X -> b 란 경로가 있고 b ->a 로 가는 경로가 존재한다면 a -> X -> b -> a -> X -> b가 성립하므로 X에 속하는 정점 k에 대해 a -> k k-> a k -> b b -> k가 성립한다. 따라서 {a X b}는 한 사이클 집합에 포함된다. 단 무향그래프(양방향그래프)의 경우엔 간선 a->b가 있다면 모든 간선을 a->b 간선이 있고 b->a간선이 있다..