미분당한 적분상수

https://www.acmicpc.net/problem/30108 30108번: 교육적인 트리 문제 $N$개의 정점을 가진 트리가 주어진다. 각 정점에는 $1$번부터 $N$번까지 번호가 중복 없이 주어지며, $1$번 정점은 트리의 루트이다. $2$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $i$번 정점의 부모 www.acmicpc.net 이 문제를 푸는 방법은 두 가지이다. 자식 노드의 값이 부모 노드의 값보다 같거나 작다는 조건을 이용할 것인가 안 할 것인가로 나뉜다. 1. 이용하지 않을 때 문제를 처음 보고 알 수 있는 것은 (선택된 모든 정점은 루트 정점이거나, 자신의 부모 정점 또한 선택되어 있어야 한다)라는 문제 조건에 의해 정점을 선택할 때 트리의 루트부터 선택하여 그의 자식들 중 하..

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/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/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 유니온 파인드와 오프라인 쿼리 테크닉으로 해결할 수 있다. "동영상 추천은 USADO가 K를 넘어야 가능하다"의 의미를 생각해 보면 간선이 제거된 상태에서, 간선의 비용이 큰 순으로 하나씩 추가하며 연결된 그룹의 정점들 수를 세면 된다는 것을 깨달을 수 있다. 쿼리를 내림차순 정렬하고, 쿼리의 k를 기준으로 간선을 조절하며 추가해 준다. 쿼리의 v가..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 세그먼트 트리와 분할 정복, 스택으로 유명한 문제이다. 제일 간단한 풀이는 스택이며, 시간 복잡도도 O(n)으로 제일 빠르다. 분할정복은 세그먼트 트리를 사용하는 방법과 사용하지 않는 방법이 있는데, 이는 둘 다 O(nlogn)으로 속도는 스택 풀이보다는 느리다. 1. 스택 O(n) 스택에는 히스토그램의 인덱스를 저장한다. 히스토그램의 높이..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 우선 순위 큐를 활용한 문제다. #include using namespace std; priority_queue pq; vector input_data; int main(){ int n; cin>>n; for(int i=0; i>p>>d; // 기간에 대해 정렬하기 위해 // 기간을 먼저 넣어 준다 input_data.push_back({d,p}); } sort..