[단계별로 풀어보기-9 기본 수학 2단계] 1978,2581,11653,1929,4948,9020,1085,3009,4153,3053,1002
집가고시퍼
2022. 1. 21. 20:22
[1978] Q : 주어진 N개의 수 중 소수가 몇개인지 찾아서 출력하는 프로그램을 작성해라 첫 줄에는 N이 주어지고, 다음 줄부터 공백을 두고 N개의 수가 주어진다.
A :공백을 두고 수들이 입력되는 것은 line 2처럼 쓰면 list로 입력받을 수 있다. 그리고 line 10에서 1은 소수가 아니다.
[2581] Q : 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것들을 모두 골라 이 소수들의 합과 소수들 중 최솟값을 줄을 바꿔 출력해라. 입력으로는 M과 N이 줄을 바꿔 입력된다. 만약 소수가 없을 경우에는 -1을 출력해라
A :행렬의 원소들의 합과 최솟값은 line 16,17처럼 할 수 있다. 그리고 line 7에서, 엄밀히 말하면 1은 모든 수에 대해 i%j==0이므로 range(2,i+1)로 바꾸고, line 10에서 cnt==1로 바꿔도 된다. 그러면 실행 시간을 줄일 수 있다.
[11653] Q : 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성해라. N이 입력되면, N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력해라. N이 1인 경우 아무것도 출력하지 않는다.
A :더 간단히 쓰려면 line 5를 while (N!=1)로 쓸 수 있다. 그러면 line 15, 16을 없엘 수 있다. 그리고 line 6,7도 없엘 수 있다. 애초에 tmp를 사용할 필요가 없어져 line 9~13에서 tmp를 N으로 고쳐써도 된다.
[1929] Q : M이상 N이하의 소수를 모두 출력하는 프로그램을 작성해라. M과 N이 빈 칸을 두고 입력된다. 소수가 하나 이상 존재하는 입력만 주어진다. 한 줄에 하나씩, 증가하는 순서대로 소수를 출력해라
A : 처음에는 기본적인 소수 판별 프로그램을 작성했지만, 시간 초과가 떴다. M과 N 사이가 커질수록 실행 시간이 오래 걸리기 때문에 시간 초과가 뜬 것이다. Line 6에서 range(2,num)으로 뒀는데 시간초과가 떴다. 소수 판별에서 실행시간을 줄이려 루트 i까지만 체크해보면 된다. 예를 들어 12는 1*12, 2*6, 3*4로 대칭적인 구조를 가지기 때문이다. 12일 때는 결국 3까지만 체크하면 되는데, 루트12 = 3.46이므로 3까지만 체크하면 되는 것이다. 루트12 * 루트12 = 12이기 때문이다. 실행 시간을 줄이기 위한 또다른 방법으로는 에라토스테네스의 체라는 대표적인 소수 판별 알고리즘을 사용해도 된다.
[4948] Q : 베르트랑 공준은 임의의 자연수 n에 대해 n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담는다. 소수의 개수를 구하는 프로그램을 작성해라. 입력으로 줄을 바꾸며 여러 n이 입력된다. 입력의 마지막에는 0이 주어진다. 1<=n<=123,456이다.
A : 처음엔 윗 문제처럼 def sosu(num)을 이용해 range(2,int(num**0.5)+1)까지 테스트했다. 하지만 이 경우에도 시간초과가 떴다. 때문에 에라토스테네스의 체를 사용해본다. 그리고 n의 범위가 아주 크지 않고, 여러 n들이 반복적으로 입력되기 때문에, 최대 범위에 대해 있는 소수들만 한 번 구해두면 각 n이 입력될 때마다 계산하지 않아도 된다. 함수를 사용할 때는 앞 line들에서 먼저 정의한 뒤, 뒷 line들에서 호출해야 한다.
[9020] Q : 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또한, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 14=7+7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성해라. 만약 가능한 n의 골드바흐 파티션이 여러가지인 경우, 두 소수의 차이가 가장 작은 것을 출력해라.(14=3+11,7+7 중 7 7 출력) 첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트케이스는 한 줄로 이루어져 있고, 짝수 n이 주어진다. 각 테스트케이스에 대해 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
A :에라토스테네스의 체를 이용해 문제를 풀었다. line 6에서 어차피 범위는 1~10000이므로 그것에 루트를 씌운 100까지만 체크하면 된다. 만약 10000이라면 루트10000까지만 체크하면 소수인지 판별이 가능하다고 했는데, 그것과 마찬가지 원리로 9999도 사실 루트 9999까지만 소수인지 체크하면 되므로 range(2,100)의 범위에 들어가는 것이다. 100~10000범위에 있는 소수들은 초기에 1을 부여받았기 때문에 0으로 값이 바뀌지 않아 그대로 sosu_list에 남는다.
이것이 처음 시도한 방법이지만, 시간 에러가 떴다. line 16부터 보면 이 방법도 sosu_list에서 n/2에 가까운 값부터 체크하고 있으면 바로 출력하고 끝내도록 했지만(소수 2부터 쭉 올라가면서 체크하는 것이 아닌), 그럼에도 시간 초과가 떴다. 문제는 line 3~12까지 sosu_list를 작성하는 과정에서 시간초과가 뜬 것으로 판단하고, 에라토스테네스의 체를 이용해 코드를 작성했다. 결국 에라토스테네스의 체를 이용해 모든 수들이 있는 list에서 소수인지 아닌지 1,0으로 표시하는 것이 소수만 모아서 list를 만드는 것보다 빠르다. 에라토스테네스의 체에서는 대략 100*(10000/i) 개의 경우에 대해 연산을 진행했지만, 아래 코드에서는 대략 10000*루트i번 연산했다. 대략 이 둘을 비교해 보자면 100/i<root(i), i>10^4/3일 때 에라토스테네스의 체가 더 빠르다. i는 1~10000의 범위이므로 대부분 10^4/3보다 크고, 때문에 이라토스테네스의 체를 사용한 방법이 더 빠르다.
[1085] Q : 직사각형의 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭지접은 (0,0), 오른쪽 위 꼭지점은 (w,h)에 있다. 직사각형 안의 점 (x,y)에서 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성해라. 입력으로 공백을 두고 x,y,w,h가 주어진다.
A :
[3009] Q : 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해 필요한 네 번째 점을 찾는 프로그램을 작성해라. 세 점의 좌표가 한 줄에 하나씩 주어지면, 직사각형의 네 번째 점의 좌표를 공백을 두고 출력해라
A :나는 이처럼 풀었지만, 더 간단히 풀려면 아래처럼 풀 수 있다. 아래처럼 푸는게 안헷갈리니 그렇게 풀도록 하자.
[4153] Q : 주어진 세 변의 길이로 삼각형이 직각인지 아닌지 구분해라. 입력은 여러 개의 테스트 케이스로 주어지며, 마지막 줄에는 0 0 0이 입력된다. 각 테스트케이스에서는 세 변의 길이가 공백을 두고 입력된다. 각 케이스에 대해 직각 삼각형이 맞다면 'right', 아니면 'wrong'을 출력해라.
A :처음에는 각 케이스에 대해 right와 wrong을 출력하도록 작성했다. line 3에서는 어차피 한 변의 길이라도 0이면 삼각형이 형성되지 않기에 if (a==0 and b==0 and c==0)으로 쓰지 않았다.
하지만 더 간단히 쓰기 위해 list를 도입할 수 있다. list.remove()를 쓰면 해당 원소를 list에서 제거할 수 있다. 예를 들어, a= [1,2,3]이면 a.remove(2) == [1,3]이다.
[3053] Q : 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 D(T1,T2) = |x1-x2| + |y1-y2|이다. 원을 평면 상의 어떤 점에서 거리가 일정한 점들의 집합으로 둘 때, 반지름 R이 주어졌을 때 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성해라. 반지름 R이 입력되면, 첫째 줄에는 유클리드 기하학에서의 원의 넓이를, 둘째 줄에는 택시 기하학에서 원의 넓이를 출력해라. 정답과의 오차는 0.0001까지 허용한다.
A :파이는 math module을 line 2에서 불러와서 math.pi로 사용할 수 있다. 처음에는 line 4와 line 5에서 %(R**2)*math.pi와 %(R**2)*2로 두었는데, 에러가 떴다. %((R**2)*math.pi)와 %((R**2)*2)로 두어야 한다.
[1002] Q : (x1,y1)에서 관측한 상대 적의 거리 r1과 (x2,y2)에서 관측한 상대 적의 거리 r2가 주어졌을 떄, 상대 적이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성해라. 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 공백을 두고 x1, y1, r1, x2, y2, r2가 주어진다. 각 테스트케이스마다 적이 있을 수 있는 위치의 수를 출력한다. 만약 적이 있을 수 있는 위치의 개수가 무한대인 경우에는 -1을 출력한다. x,y는 -10000이상 10000이하의 정수이며, r은 10000 이하의 자연수이다.
