초보 개발자의 이야기, 릿허브

1. 문제이해 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 다음과 같은 규칙을 따르되, N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 구현하는 것이 목표이다. 1. 2부터 N까지 모든 정수를 적는다. 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 2. 문제풀이 2부터 N까지의 자연수를 입력받고, K번째 지워지는 숫자를 찾는 문제..

1. 문제이해 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net M 이상 N 이하의 자연수 중 소수인 것을 찾아 해당 값들의 합과 값들 중 최솟값을 출력하는 것이 목표이다. 2. 문제풀이 M 이상 N 이하의 소수를 모두 찾아 해당 값들의 합과 최솟값을 출력하는 문제이다. 이전에도 비슷한 문제를 풀이한 적이 있어서, 해당 방법과 비슷한 방법으로 풀이했다. 제곱근 값(루트값)을 기준으로, 앞의 있는 수들과 뒤에 있는 수들은 서로 짝을 이루므로, 제곱근 값을 기..

1. 문제이해 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 테스트 케이스의 개수와 테스트 케이스의 개수만큼 두 자연수 A, B가 주어질 때, A, B의 최소공배수를 출력하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 T개의 A와 B를 입력받아, 각각의 최소공배수를 출력하는 것이 목표이다. 이전 포스팅에서 두 수의 최대공약수와 최소공배수를 구하는 문제를 풀이한 적이 있었는데,이 문제에도 해당 문제와 동일한 알고리즘을..

1. 문제이해 1037번: 약수 (acmicpc.net) 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 1과 정수 N을 제외한 정수 N의 약수들을 입력받아, 정수 N을 구하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 정수 N의 약수들 (단, 1과 자기자신은 제외) 을 입력받아 N을 구하는 것이 목표이다. 약수가 모두 주어졌으므로, 생각보다 간단한 문제이다. 예를 들어, 구하고자 하는 N이 18이라고 가정해보자. 18의 진짜 약수는 1과 18을 제외한 나머지 약수들, 2, 3, 6, 9 이다...

1. 문제이해 4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 입력받은 자연수 n에 대해 n보다 크고, 2n보다 작거나 같은 수 중 소수의 개수를 출력하는 것이 목표이다. (입력의 마지막에는 0이 주어진다.) 2. 문제풀이 주어진 n에 대해, n n; count = 0; if (n == 1) {// n이 1인 경우 count = 1; } else { for (int i = n + 1; i

1. 문제이해 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 수의 개수와 숫자들을 입력받아, 해당 숫자들 중 소수가 몇개인지를 출력하는 알고리즘을 구현하는 것이 목표이다. 2. 문제풀이 문제 그대로, 숫자들을 입력받아, 그 중 소수의 개수를 출력하는 것이 목표이다. 여기서 소수란, 1과 자기 자신만을 약수로 가지는 수를 이야기한다. 따라서, 1보다 큰 수 중에서 1과 자기자신이 아닌 다른 숫자로 나누어지면, 그 수는 소수가 아닌 것이다. (이를 합성수라고한다.) 이 점에 착안하여, 해당 숫자를 1. 2부터 자기..