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를 돌려서 가장 큰 값이 나온다면 그 값이 지..

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 그래프에 입력받고 DFS이던 BFS이던 해준 뒤에 2부터 N까지의 부모 노드를 저장해주면 된다. #include #include #include using namespace std; vector ar; bool vis[100001]; map M; void dfs(int cur) { vis[cur] = true; for (auto i : ar[cur]) { if (!vis[i]) { M[i] = cur; dfs(i); } } } int main() { ios::sync_wit..