시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 10607 5410 4584 51.627% 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다. 예제 ..

알고리즘 문제해결 전략 1권에서 설명한 내용은 이렇다. 유클리드 알고리즘은 두 수 p,q(p>q)의 공약수의 집합은 p-q와 q의 공약수 집합과 같다는 점을 이용한다. 증명 a,b의 공약수 g가 있다고 할때, a=ag, b=bg 로 쓸 수 있다. 그러면 a-b=(a-b)g 이므로 g는 a-b와 b의 공약수이기도 하다. 반대 방향도 같은 방법으로 보일 수 있다. 따라서 a,b의 최대공약수 gcd(a,b)는 항상 a-b와 b의 최대공약수 gcd(a-b,b)와 같다. 이 성질을 이용해 6과 15의 최대공약수를 구해보면.. gcd(6,15) = gcd(9,6) = gcd(3,6) = gcd(3,3) = gcd(0,3) 이 과정을 반복하면 이와 같이 결과적으로 어느 한 수가 0이 된다. 0과 3의 최대공약수는 3..

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 10540 4729 3948 45.806% 문제 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. 예제 입력 2 7 3 5 예제 출력 31 35 소..

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 7158 1538 1078 22.154% 문제 K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자. 예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다. K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다. 입력 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의..

git에서 clone 받는 과정에서 Filename too long 에러로 인해 실패하는 경우가 있다. 이는 윈도우 API의 파일경로길이 제한이 260자이기 때문이다. 이 제한을 없애려면 아래와 같이 git 설정을 변경한다. git config --system core.longpaths true

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 14784 9033 6904 62.741% 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 ..