미분당한 적분상수

https://www.acmicpc.net/problem/16950 16950번: 레드 블루 스패닝 트리 2 첫 줄에는 세 정수 n, m, k가 주어진다. n은 그래프의 정점의 개수 (2 ≤ n ≤ 1,000)이고, m은 간선의 개수, k는 문제에 설명되어 있는 파란색 간선의 개수 (0 ≤ k < n) 이다. 다음 m개 줄에는 간선의 정 www.acmicpc.net 이 문제를 풀기 위해서는 (백준 4792 레드 블루 스패닝 트리)의 내용을 꼭 알고 있어야 한다. 위 링크의 글에서 설명했듯이 파란 간선이 t개인 mst에서 t+1인 mst를 만들려면 정점 u, v를 잇는 사용되지 않은 파란색 간선을 찾고, 스패닝 트리에서 u에서 v로 가는 경로중 빨간색 간선을 지우고 파란색 간선을 추가하면 된다. 이를 그대..

https://www.acmicpc.net/problem/25545 25545번: MMST 첫째 줄에 그래프의 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 200\,000$, $N-1 \leq M \leq 500\,000)$ 둘째 줄부터 $M$줄에 걸쳐 $i$번째 간선의 정보가 $(U_i, V_i, C_i)$와 같이 주어진다. 이는 www.acmicpc.net 문제에서 말하는 MMST는 Minimum Spanning Tree(최소 신장 트리)도 아니고 Maximum Spanning Tree(최대 신장 트리)도 아닌 신장 트리이다. MMST를 구하는 방법이 따로 있는지는 모르겠다. 하지만 일반적인 MST보다 MMST의 수가 압도적으로 많기 때문에 최소 신장 트리와 최대..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 삼차원 공간 상에 있는 점들을 최소비용으로 연결하는 문제이다. 점의 개수 n은 100,000개 이하기 때문에 모든 간선들을 만들면 nC2개일 것이고, 메모리, 시간 둘 다 부족할 것이다. 이를 해결하기 위해 필요한 간선만을 만들어 주는 게 문제 해결법이다. 비용이 min(|Xa-Xb|, |Ya-Yb|, |Za-Zb|) 이기 때문에 비용 계산에 x축이나 y축, z축이..

https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 일단 간단하게 해답을 말하자면 스패닝 트리들 중에서 파란색 간선의 최대 개수를 B_MAX, 최소 개수를 B_MIN이라 하자. B_MIN ≤ t ≤ B_MAX 라면, 파란색 간선이 t개인 스패닝 트리도 존재한다. 따라서 B_MIN, B_MAX를 구해주면 된다. 그렇다면 왜 저런 명제가 성립할까 어떠한 스패닝 트리의 파란색 간선 개수를 t라 하자. 최대 최소를 넘어가지 않는 선에서 t+1인 스..

https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net bfs 또는 dfs로 해결할 수 있다. 쿼리가 최대 5,000개가 주어지고 정점도 최대 5,000개가 주어지므로 시간 복잡도 O(N*Q)로 해결할 수 있다. 각 쿼리마다 dfs를 돌리자. 동영상 추천은 USADO가 K를 넘어야 가능하므로, 현재 정점에서 다음 정점으로 가는 비용이 K를 넘는 경우만 가능하다. 그런 정점들의 개수에서 처음 시작한 정..

https://www.acmicpc.net/problem/26656 26656번: 점프킹 점프킹은 엄청난 점프력을 가진 초인이다. 어느 날, 점프로 세계를 여행하던 점프킹은 착지를 잘못해 점프 감옥에 갇히게 되었다. 점프 감옥은 $N$행 $M$열의 격자이며, 각 칸에서는 주어진 방향 www.acmicpc.net 그래프 이론에 골드 1의 문제이기 때문에 문제를 풀기 위해 생각해야 할 것은 많지 않다. 그냥 생각나는 데로 구현하다 보면 풀리는 물제이다. 탈출가능한 칸과 불가능한 칸의 분리 집합을 각각 만들어둔다. 탈출가능한 분리집합 중 한 집합에서는 출구?(밖으로 나가게 되는 칸)이 무조건 한 칸이므로 한 칸만 조작하면 이 집합을 탈출 불가능하게 만들 수 있다. 이걸 역으로 생각하면 탈출 불가능한 집합도 한..

https://www.acmicpc.net/problem/17490 17490번: 일감호에 다리 놓기 2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다. www.acmicpc.net 크루스칼을 사용하여 풀었다. 공사하는 구간을 체크해 놓은 뒤 어느 구간이 공사를 하지 않는지 찾아서 그 구간을 가중치가 0인 간선으로 추가했다. 강의동은 1번부터 N번까지 있으므로 와우도를 0번 강의동으로 놓고 돌다리의 돌 개수를 가중치로 하는 간선을 추가한다. 만약 공사하는 구간이 1 이하이면 모든 강의동이 연결되어 있으므로 예외처리 해준다. 공사하는 구간이 2 이상이면 0번 노드부터 N번 노드까지 최소 스..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름 구하기는 유명하기에 그 해법도 잘 알려져 있다. 1. 임의의 한 노드에서 dfs를 실행하여, 제일 멀리 떨어져 있는 노드를 찾는다. 2. 1에서 찾은 노드를 시작으로 dfs를 재실행하여 제일 멀리 떨어져 있는 노드를 찾는다. 3. 1에서 찾은 노드와, 2에서 찾은 노드사이의 거리가 트리의 지름이다. // 간단한 코드 설명 preprocess() : 입력을 받는 함수이다..

https://www.acmicpc.net/problem/2585 2585번: 경비행기 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간 www.acmicpc.net 비행장을 노드로 생각하고, 모든 노드가 상호 연결된 완전 그래프(Complete Graph)를 만든다. 이때의 가중치를 노드끼리의 거리로 두면 된다. 매개 변수 탐색을 하며 두 가지를 확인한다. 1. 연료통의 크기가 출발점에서 도착점으로 갈 수 있는지 bfs를 통해 판단한다. 2. visited 배열을 만들어 몇 번째 이 노드를 방문했는지 기록하고, 도착점까지 k번 안에 왔는지 확인한다. 구현만 잘해주면 ..

https://www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라를 여러 번 돌려서 푸는 문제였다. dist[i][j] : i에서 j로 가는 최소 비용이라고 정의하자. 1. 정점의 수만큼 반복을 돌며, 정점의 수만큼 다익스트라를 실행한다. 2. i에서 j로 갈 때, 정점 i 에서 기름값으로 정점 j로 가는 비용은 dist[i][j]*(정점 i에서의 기름값)이다. 이 비용을 value라 할 때, 정점 i, j를 잇는 가중치가 v..