www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색에 대해 공부하는 중이다. 간단한 문제지만 L, R 정하거나 ans값을 찾는 것이 한 번에 되지 않아서 연습해볼 만하다. 정부는 지방마다 각 예산을 할당해야 되는데 예산이 정해져 있어서 우선순위를 둬야 한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상..

www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 머리가 아파오는 수학 문제다. 이 문제는 해답을 참고해서 풀었다. 기본적으로 페르마의 소정리를 이용 확장 유클리드 호제법을 이용 이외에 소인수 분해로 푸는 방법이 있는 것 같은데, 나는 페르마의 소정리를 이용해서 풀었다. 페르마의 소정리는 소수 p와 정수 a에 대해 다음을 만족한다. $$a^{(p-1)}\equiv1\;(mod\;p)$$ 따라서 $$nCk = \frac{k!}{(n-k)!}$$ 에서 n! = A, k!(n-k)! = ..

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제의 내용은 간단하다. 처음에는 map이나 set을 사용해서 각각의 탐색은 O(log N)이니 찾을 수 있을 것 같았지만 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, x; vector ar; map M; c..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 단계별로 풀기에서 힙을 공부하고 응용 겸 풀어본 문제이다. 처음에는 이거 벡터로 해야되는거 아닌가? 싶을 정도로 접근이 안돼서 다른 사람의 풀이를 참고했다. 최대 힙과 최소 힙을 조건에 맞게 나눠서 그때 그때 최대 힙의 top을 출력해주면 된다. 최대힙의 크기는 최소 힙의 크기와 같거나 1만큼만 커야 한다. 최대힙의 top은 최소 힙의 top보다 작아야 한다. 이 두 조건을 만족시키며 구현하면 ..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 �� www.acmicpc.net 이 문제도 1967번과 똑같은 문제다. 다만 입력받는 방식이 조금 귀찮아졌다. 마찬가지로 1번 노드에서 DFS를 돌리고 최댓값의 인덱스를 저장해 두었다가 다시 DFS를 돌리면 된다. #include #include #include using namespace std; bool vis[100001]; vector ar[100001]; int ans, idx; void dfs(int cur, int..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net 무방향 그래프가 가중치를 포함하여 주어진 트리에서 트리의 지름을 구하는 문제이다. 지름은 가중치가 가장 긴 값이 지름이 된다. 문제는 이해가 되는데 트리의 지름에 대한 개념이 없어서 어떻게 풀어야 할지 감이 안 잡혀 다른 분들의 코드를 참고했다. 정해는 부모 노드에서 DFS를 돌려서 가장 큰 값이 나온 그 노드를 저장하고, 그 노드에서 다시 DFS를 돌려서 가장 큰 값이 나온다면 그 값이 지..