HTD

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net - 관찰 예제 입력 1의 카드들을 정렬해보면 다음과 같다. 2 3 4 5 7 8 9 이제 K번 주어지는 철수가 내는 카드들을 살펴보자. 4를 내면 5가 나와야하고, 1을 내면 2가 나와야한다. -> 이진탐색 lower_bound를 입력값 + 1에 대해 해준다.(4를 냈다면 5를 찾는 탐색을 진행) 다음으로 카드가 1 2 3 4가 있는데, 0을 ..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #define REP(i, a, b) for(int i=(a);i> N >> K; // Get (K!(N-K)!)^1000000005 long long t = getFactorial(K) * getFactorial(N - K) % MOD; long long res = getPower(t, MOD - 2); // res * N! cout

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 10 = 2 * 5에서, 2와 5의 승수만을 고려하여 풀 수 있다는 아이디어를 내야한다. nCr = n! / (r! * (n-r)!)의 각각의 팩토리얼에서 2, 5의 승수를 가져와서 연산을 해주면 된다. 예를 들어, 5C3 = 5!/(3!*2!) = (1*2*3*4*5) / ((1*2*3) * (1*2))에서 5!, 3!, 2!에는 각각 2^1, 5^1 / 2^1 / 2^1가 포함되며 2^(-1), 5^0이므로 0의 개수가 0이다. 만약 어떤 조합에서 2^..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { int var; int index; struct Node* next; }Node; typedef struct Stack { int size; Node* top; }Stack; Node* getNode(int var, int index) { Node* res = malloc(sizeof..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { struct Node* prev; struct Node* next; int value; }Node; Node* getNode(int value) { Node* newNode = malloc(sizeof(Node)); newNode->value = value; return ..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct TwoInt { int n1, n2; }TwoInt; void printNumbers(int* nums, int length) { for (int i = 0; i < length; i++) printf("%d\n", nums[i]); } TwoInt divideNumsWithPivotAndGet..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) void printNumbers(int* nums, int length) { for (int i = 0; i < length; i++) printf("%d\n", nums[i]); } void doMerge(int* nums, int left, int right) { int mid = (left + right) / 2; ..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct PriortyQueue { int* H; int length; }PriortyQueue; void printNumbers(int* nums, int length) { for (int i = 1; i < length+1; i++) printf("%d\n", nums[i]); } void swapN..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) void printNumbers(int* nums, int length) { for (int i = 0; i < length; i++) printf("%d\n", nums[i]); } void swapNumbers(int* nums, int index1, int index2) { int tmp = nums[index1];..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) void printNumbers(int* nums, int length) { for (int i = 0; i < length; i++) printf("%d\n", nums[i]); } int findMinStartingAt(int* nums, int length, int start) { int minIndex = star..