🎈 개 요
3주차 코딩테스트 준비로는 수학과 관련된 백준 문제들을 풀이하였다.
🗑 에라토스테네스의 체
학습 계기
골드바흐의 추측(4보다 큰 모든 짝수는 (홀수 + 홀수)) 문제를 해결하다 학습하게 된 부분. 원래 소수를 찾는 문제들을 접근할 때 항상 2부터 시작해서 해당 숫자까지 for루프를 돌면서 한 번이라도 나눠진다면 해당 수가 소수라고 판단, 루프를 다 돌았다면 소수라고 판단했는데, 해당 문제는 시간을 0.5초로 제한이 되어있어서 다른 방법을 찾게 되었고 마땅히 떠오르지 않아 검색을 해보며 에라토스테네스의 체이다.
개념
에라토스테네스의 체는 말 그대로 체를 사용해서 우리가 원하는 것만 골라내는 느낌의 개념이다. 소수를 찾아내는데 있어서 가장 최적화된 알고리즘 방법으로, 파이썬으로 접근할 시 배열을 하나 두고, 체에 걸려가며 소수 값들만을 표시해두게 되는 방식으로 진행한다.
array = [True for i in range(1000001)]
for i in range(2, 1001):
if array[i]:
for k in range(i + i, 1000001, i):
array[k] = False
구하고자하는 크기가 100만임에도 1001까지만 진행하는 이유는 소수를 구하는데 제곱근의 성질의 적용하기 때문이다. 제곱근의 성질은 예를 들어 18일때 18의 약수는 1,2,3,루트18, 6,9,18 이기 때문에 해당 숫자가 소수인지 확인하려면 루트 18이하의 숫자들로만 나누어봐도 알기 때문이다.
그리하여 1001이하의 숫자들 중 ary에 값이 True인 경우 해당 숫자로 나누어지는 숫자들을 전부 False처리를 해준다.
[G2][2749] 피보나치 3
# 피보나치 수열을 만들자
a = int(input())
result = 1
if(a == 1):
result = 1
elif(a == 2):
result = 1
b = result
c = result
if(a >= 3):
for i in range(a-2):
result = b + c
b = c
c = result
print(result)
print(result%1000000)[S2][11051] 이항 계수 2
이항 계수라는 말 자체가 무슨 의미인 몰라 검색을 하였다. 문제 설명 부분에서 nCr 느낌의 조합 그림이 보이긴 했는데 확실치 않았다. 검색을 해보니 조합이 맞았고 문제 풀이를 진행하였고 정답을 받을 수 있었다. 3주차에서 같이 풀이하고 있는 재귀를 이용해서 문제를 해결해보았다.
import sys
sys.setrecursionlimit(10**5)
def factorial(n, cnt, tar):
if(n > 1 and cnt != tar):
cnt += 1
return n * factorial(n-1, cnt, tar)
else:
return 1
N,K = map(int,input().split())
s1 = factorial(N,0,K)
s2 = factorial(K,0,K)
s3 = s1//s2
print(int(s3%10007))[S1][6588] 골드바흐의 추측
문제에 접근하기 전 정답 비율이 가장 먼저 눈에 띄는데 정답 비율이 23%에 불과하여 문제를 풀기 전 조금 겁을 먹고 시작하였다.
- 4보다 큰 모든 짝수는 (홀수 + 홀수) 로 나타낼 수 있다
- 이때 수를 입력 받고 해당 숫자를 두 홀수의 덧셈으로 나타내라
- 방법이 많다면 b-a가 가장 큰(즉, 두 수 간의 차이가 큰) 것을 출력
방법1. 앞에서부터 소수 하나, 뒤에서부터 소수 하나 덧셈
방법2. 받은 수에 대한 소수들을 전부 배열에 저장하고, 해당 숫자들을 조합
#방법1 : 하다 답답해서 다른 방법 선택
n = 1
while(n != 0):
n = int(input())
on = 0
a1 = 0
a2 = 0
if(n%2 != 0):
print('님 추측 틀리심')
continue
for i in range(n-2, 2, -1):
if(on == 1): break
for j in range(2, i, 1):
if(i % j == 0):
break
if(j == i-1):
print(i,'는 소수다')
on = 1
a1 = i
on = 0
for k in range(2, n-2, 1):
if(on == 1): break
for m in range(2, k, 1):
if(k % m == 0):
break
if(m == k-1):
if(a1 + m == n):
print(a1,m,n,k)
print(k,'는 소수다')
a2 = k
print(a1, a2)#방법2 : 시간 초과
import sys
n = 1
while(n != 0):
n = int(sys.stdin.readline())
ary = []
find = 0
if(n%2 != 0):
continue
for i in range(2, n-2, 1):
for j in range(2, i, 1):
if(i % j == 0):
break
if(j == i-1):
ary.append(i)
for a in ary:
if(find == 1): break
for i in range(len(ary)-1, 0, -1):
if(a + ary[i] == n):
print(n, '=' ,a,'+', ary[i])
find = 1
[G1][1016] 제곱 ㄴㄴ수
1차
# 1000000000000
mi, ma = map(int, input().split())
ary = [True for i in range(ma)]
num = 2
cnt = 0
if(mi == ma):
print(1)
else:
if(ma >= 4):
for i in range(2, ma//2, 1):
a = i * i
value = a
while(value <= ma):
ary[value-1] = False
value += a
for j in range(mi, ma, 1):
if(not ary[j]):
cnt += 1
print('--------------')
print(ma - cnt)
2차 수정
# 1000000000000
mi, ma = map(int, input().split())
ary = [True for i in range(ma)]
num = 2
cnt = 0
if(mi == ma):
print(1)
else:
if(ma >= 4):
for i in range(2, ma, 1):
a = i * i
if(a > i*i):
break
value = a
while(value <= ma):
ary[value-1] = False
value += a
for j in range(mi, ma, 1):
if(not ary[j]):
cnt += 1
print('--------------')
print(ma - cnt)
3차 수정
-제곱수들로 안에서 나눠지는 숫자 존재 시 cnt + 1
# 1000000000000
mi, ma = map(int, input().split())
num = 2
cnt = 0
if(mi == ma):
print(1)
else:
if(ma >= 4):
for i in range(2, ma):
print(i, ma)
a = i * i
if(a >= ma):
print('끝', a, i)
break
value = a
# 근데 이렇게하면 겹치는 숫자가 문제가 될 것 같다.
# 예를 들어 2의 제곱인 4로 막 지우다보면 16의 제곱인 숫자도 지워진다.
while(value <= ma):
value += a
cnt += 1
print('--------------')
print(ma - cnt)
4차 수정
-새로 배열을 만들어 그 장소에 제곱수들을 저장했다-
# 1000000000000
mi, ma = map(int, input().split())
ary = []
cnt = 0
if(mi == ma):
print(1)
else:
if(ma >= 4):
for i in range(2, ma):
print(i, ma)
a = i * i
if(a >= ma):
print('끝', a, i)
break
value = a
while(value <= ma):
if(not ary.__contains__(value)):
ary.append(value)
value += a
print('--------------')
print(ma - len(ary))
