Per ardua ad astra.

문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. ..

문제 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) 출력 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다. 예제 입력 1 3 1 45000 6 10 13 17 예제 출력 1 45000 30 221 알고리즘 분류 ..

최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm) 최대 공약수(GCD; Greatest Common Divisor(Factor)) 두 개 이상의 자연수들의 공통인 약수들의 모임을 공약수(Common Divisor)라고 하고, 공약수 중에서 가장 큰 수를 최대 공약수(Greatest Common Divisor)라고 한다. 예) $12$의 약수는 $\{1, 2, 3, 4, 6, 12\}$ 이고 $18$의 약수는 $\{1, 2, 3, 6, 9, 18\}$일 때, 두 수 $12$와 $18$의 공약수는 $\{1, 2, 3, 6\}$이고 최대 공약수는 $6$이 된다. 코드 int gcd(int x, int y) { for (int i = (x > y ? y : x..

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 예제 입력 1 24 18 예제 출력 1 6 72 출처 Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 1번 Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 고등부 1번 알고리즘 분류 수학 정수론 유클리드 호제법 문제 출처 https://www.acmicpc.net/problem..

알고리즘이란? 알고리즘의 개념 알고리즘(algorithm) : 주어진 문제를 해결하는 절차(Procedure) 각 단계는 기본적인 연산(Operation) 하나로 이루어져 있을 수도 있고, 혹은 다른 부분 문제(Subproblem)에 대한 알고리즘일 수는 있지만 충분히 구체적이어야 한다. 알고리즘의 조건 일반적으로 알고리즘은 다음의 두 조건을 반드시 만족해야 한다. 종료(termination) : 모든 가능한 입력 사례에 대하여 반드시 끝난다. 정확성(correctness) : 모든 가능한 입력 사례에 대하여 옳은 답을 출력한다. 좋은 알고리즘 자원(Resource)을 적게 쓰는 알고리즘이 좋은 알고리즘이라고 할 수 있다. 가능한 입력에 대하여 항상 종료하고 옳은 답을 출력하면 알고리즘이 되지만, 실행시..