IT 기획의 길

문제 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다. 출력 가능한 D값의 최댓값을 출력한다. 알고리즘 설계 수빈이의 위치 S에서 동생들이 있는 위치 A1,A2 -- An..

문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. GCD가 뭔지도 안알려주는 문제설명을 보고 실망하였다 구글에 검색해보니 최대공약수였다 ㅎㅎ.. 상식인가? 암튼 문제를 요약하자면 1. 첫줄에 테스트 케이스 개수를 입력하고 2. 각줄의 수의 개수 / 수 를 입력한다 3. 입력한 수를 모두 짝을 이루고 짝을 이..

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ..

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 알고리즘 설계 일단 에라토스테네스의 체 문제를 풀고 와가지고 본 이 문제는 딱 봤을때 쉬웠다 그런데 정답률이 27퍼밖에 되지않았던 이유는 에라토스테네스의 체로 풀지않으면 시간초과가 나는 문제였다 이전에 풀었던 에라토스테네스의 체 문제는 규칙에 따라 수를 삭제 하고 몇번째 삭제한 수가 몇이냐는 걸 묻는 문제였고 이 문제는 규칙에 따라 수를 삭제하고 해당 범위내의 소수를 출력하라는 문제였다 1. 소수인걸 true 소수가 ..

문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다. 알고리즘 설계 1. 일단 크기가 n+1인 배열을 만들어 2부터 n+1까지의 수를 입력한다 2. 삭제한 수를 0으로 만든다 3..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 알고리즘 설계 1. 소수란 1과 자기자신만을 약수로 갖는 1보다 큰 수를 말한다 2. 소수냐 아니냐를 true & false로 지정한다 3. 1은 무조건 false이다 4. 2보다 크고 자기 자신보다 작은 수로 나눠지는 경우가 1번이라도 있는 수는 소수가 아니다 5. 3,4를 통과한 수는 소수이다 6 count변수로 입력한 수중 소수가 몇개인지 check한다 7. if(prime(arr[i])){ count++; } 를 사용하여 true인 경우 ..