기록보관소

이항 계수 2문제는 이항 계수 점화식뿐만 아니라 다이나믹 프로그래밍 기법을 활용하는 문제입니다. (n, k) = (n-1, k-1) + (n-1, k)라는 사실과 배열을 활용하여 (n, k)를 미리 계산한 후 출력함으로써 풀 수 있습니다. 다이나믹 프로그래밍을 할 때 기교를 발휘하면 배열의 크기는 1차원 배열 [1001]까지 줄일 수 있습니다. 작성한 코드에서는 2차원 배열 [2][1001]로 작성하였습니다. #include //NCK int N, K; int result[2][1001]; int i=1; int main(void) { scanf("%d %d", &N, &K); result[0][0] = 1; result[1][0] = 1; while (1) { for (int j = 1; j < 100..

링 문제는 원주의 비율과 최대공약수를 활용하는 문제입니다. 원주가 반지름에 비례한다는 사실을 이용하여 회전수를 구하고 최대공약수를 이용하여 기약분수 형태로 출력함으로써 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include //기약분수는 최대공약수로 생성 int N; int temp, temp1, temp2; int gcd(int a, int b) { int temp; if (a < b) { temp = b; b = a; a = temp; } while (a % b != 0) { temp = b; b = a % b; a = temp; } return b; } int main(void) { scanf("%d", &N); scanf("%d", &temp1); for (int i = 0;..

이항 계수 1 문제는 조합의 식을 이용하는 문제이다. nCk = n!/(n-k)!/k!이라는 사실을 이용하여 for문으로 값을 계산하면 된다. 작성한 코드는 다음과 같다. #include //NCK int N, K; int result = 1; int main(void) { scanf("%d %d", &N, &K); for (int i = 0; i < K; i++) { result = result * N / (i + 1); N--; } printf("%d\n", result); } 문제의 지문은 다음의 링크에서 확인할 수 있다. https://www.acmicpc.net/problem/11050

검문 문제는 최대공약수를 활용하는 문제이다. 두 수를 어떤 수로 나누었을 때 나머지를 같게 하는 수는 두 수의 차의 모든 약수이다. 또한 두 수의 차의 모든 약수는 두수를 나머지가 같게 나눈다. 위의 명제는 귀류법과 a=bq+r의 식을 활용하여 증명할 수 있다. 위의 두 문장은 두 수를 나누었을 때 나머지를 같게 만드는 어떤 수가 두 수의 차의 약수와 동일하다는 것을 알려준다. M개의 수를 나머지가 같게 만드는 어떤 수를 찾아야하므로 M개의 수를 정렬하고 순차적으로 두 수의 차의 최대공약수를 계산하여야 한다. 최종적으로 M개의 수를 나누었을 때 같은 나머지를 같게 하는 어떤 수들을 약수로 같는 최대공약수가 얻어진다. 이 최대공약수의 모든 약수를 출력함으로써 문제는 해결된다. 주의할 점은 마지막에 구한 최..

최소공배수 문제는 최대공약수와 최소공약수의 관계를 활용하여 해결할 수 있다. 두 수를 최대공약수로 나누었을 때의 몫들과 최대공약수를 곱하면 최소공배수를 구할 수 있다는 특성을 이용하여 문제를 해결합니다. 최대공약수는 유클리드 호제법을 이용하여 O(lgn)으로 구할 수 있습니다. 유클리드 호제법에 대한 내용을 다음과 같습니다. 2021.07.10 - [알고리즘/이론] - [알고리즘/이론][정수론] 유클리드 호제법 [알고리즘/이론][정수론] 유클리드 호제법 두 양의 정수 a, b에 대해서 a를 b로 나눈 나머지로 다시 b를 나누는 과정을 반복했을 때 마지막에 나머지가 0일 때 나누는 수가 a, b의 최대 공약수가 된다는 정리이다. 증명 a와 b를 동시에 나누는 ark-hive.tistory.com 작성한 코..

두 양의 정수 a, b에 대해서 a를 b로 나눈 나머지로 다시 b를 나누는 과정을 반복했을 때 마지막에 나머지가 0일 때 나누는 수가 a, b의 최대 공약수가 된다는 정리이다. 증명 a와 b를 동시에 나누는 약수는 b로 a를 나누었을 때 나오는 나머지와 b를 동시에 나눈다. a는 b의 배수와 나머지의 합으로 표현되는 데 b는 공통인 약수로 나누어지기 때문에 나머지 또한 공통인 약수로 나누어져야만 a가 나누어질 수 있다. 따라서 공통인 약수는 b와 나머지 사이에서도 공통이 된다. 또한 최대 공약수 또한 같아진다. 만약 최대 공약수가 다르다고 가정하면 나머지와 b사이의 최대공약수는 a와 b를 동시에 나눌 수 있기 때문에 모순이 생기게 된다. 이러한 최대공약수가 공통인 특성을 이용하여 반복적으로 수식을 계산함..

최대공약수와 최소공배수 문제는 최대 공약수와 최소공배수의 특성을 이용한 문제입니다. 두 수에 대한 기본 정의를 활용하여 문제를 해결할 수 있습니다. for문을 사용하여 모든 수에 대해 특성을 만족하는지 나누어서 확인하면 됩니다. 최대 공약수는 1부터 작은 수까지, 최대 공배수는 큰 수보다 크다는 점을 이용하면 for문 반복 횟수를 줄일 수 있습니다. 작성한 코드는 다음과 같습니다. #include int A, B; int GCD; int temp; int main(void) { scanf("%d %d", &A, &B); if (A > B) { temp = A; A = B; B = temp; } for (int i = 1; i

약수 문제는 약수의 성질을 이용하는 문제입니다. 어떤 수의 모든 약수가 주어졌을 때 가장 작은 약수와 가장 큰 약수를 곱하면 어떤 수가 된다는 성질을 이용하면 됩니다. 작성한 코드는 다음과 같습니다. #include int N; int min = 987654321; int max = 0; int temp; int main(void) { scanf("%d", &N); for (int i = 0; i max) max = temp; } printf("%d\n", min * max); } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/pr..