기록보관소

이항 계수 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 작성한 코..

최대공약수와 최소공배수 문제는 최대 공약수와 최소공배수의 특성을 이용한 문제입니다. 두 수에 대한 기본 정의를 활용하여 문제를 해결할 수 있습니다. 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..

배수와 약수 문제는 정수의 특성을 활용하는 문제이다. 서로 같지 않은 자연수는 약수 관계, 배수 관계, 아무것도 아닌 관계 중 1가지를 가지게 된다. 이 점을 유의하여 나머지를 기준으로 분류하여 요구하는 문장을 출력하면 된다. 작성한 코드는 다음과 같다. #include int num1, num2; int main(void) { while (1) { scanf("%d %d", &num1, &num2); if (num1 == 0 && num2 == 0) break; else { if (num2 % num1 == 0) { printf("factor\n"); } else if (num1 % num2 == 0) { printf("multiple\n"); } else { printf("neither\n"); } ..

AC문제는 큐를 활용한 문제이다. 큐의 pop을 활용하는 문제로 뒤집기 함수로가 추가된 문제이다. 뒤집기의 경우 pop할 때 경우에 따라 head와 tail 중 1개를 선택하여 1만큼 이동시키면 된다. 주의할 점은 테스트 케이스의 입력이 큰 편이라 수행시간에 여유가 없다는 점이다. 가능하면 O(n+p)의 시간에 수행하여야 한다. 문제를 풀면서 놓쳤던 부분은 다음과 같다. 먼저 모든 처리를 하고 출력을 할 때 출력형식에 맞추어 출력하는 것에 모든 것의 성패가 달렸다는 점을 느낄 수 있었다. 다 풀었다고 느꼈을 때 자만하지 말고 끝까지 주의를 기울여 풀어야 한다는 점이다. 입력에서도 입력 버퍼에 무엇이 있는지 주의를 기울여야 한다는 점이다. ps에서 끝까지 방심하지 말라는 교훈을 얻은 것 같다. 작성한 코드..

회전하는 큐는 데크를 사용하여 푸는 문제입니다. front에서만 pop이 될 수 있으므로 뽑아낼 원소의 위치와 front사이의 가능한 두 개의 거리를 비교하여 거리가 작은 쪽으로 로테이션합니다. 뽑아낼 원소를 모두 뽑아내기 위해 로테이션하는 총 횟수를 계산하여 출력함으로써 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include #define size 100 int N, M; int extracted[100]; int index_extracted; int total_op; int deque[size]; int front = 0, back = 1; int temp_front, temp_back; void rotate_clock() { deque[back]=deque[(front+1+si..