목차
1. 나머지 3052
- 수 10개를 입력 받은 뒤, 이를 42로 나눈 나머지를 구한다.
- 그 다음 서로 달느 값이 몇 개 있는지 출력하는 프로그램 작성
- 수 10개를 입력 받는다.
- 나머지를 담을 집합 선언
- for문을 돌면서 42로 나누었을 때 나머지를 집합에 넣는다.
- 집합의 원소 개수 출력
S = set()
for i in range(10):
T = int(input())
S.add(T % 42)
print(len(S))
배운 것
- set은 dict 타입과 동일한 중괄호를 사용하므로, 중괄호 만으로 생성할 수 없다.
- 따라서 set() 생성자를 사용한다.
- ※ 원소 추가는 add
- ※ 여러 값을 한번에 추가할 때는 update
- ※ 원소의 제거는 remove
- ※ copy는 얕은 복사
- 집합 관련 메소드 참고
2. 최대공약수와 최소공배수 2609
- 두 개의 자연수를 입력 받아 최대공약수와 최소공배수 출력
유클리드 호제법 기억해야한다. (a>b)a,b에 대해서 a를 b로 나눈 나머지가 r이라고 한다면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r을 구하고, r을 r2로 나눈 나머지를 구하는 과정을 반복하여 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
- 0으로 나누어 떨어지지 않는 수가 나올 경우도 고려해주어야 한다.
def GCF(a, b): # greatest common facter
while True:
a, b = b, a % b
if not b: # 0으로 나누어 떨어지지 않으면
return a
elif not a % b:
return b
def LCD(a, b):
lcd = GCF(a, b)
return a*b//lcd
a, b = map(int, input().split())
print(GCF(a, b))
print(LCD(a, b))
배운 것 복습
def gcd(m,n):
while n:
t = m%n
m,n = n,t
return abs(m)
- 위 코드가 훨씬 깔끔하다.
- while 문의 조건에 n을 넣어줘서, 따로 if문을 걸어줄 필요를 없앴으며
- 4,2와 같은 0으로 % 연산을 하게 되는 경우도 방지할 수 있다.
3. 최소공배수 1934
def GCD(a, b): # greatest common divisor
while b:
t = a % b
a, b = b, t
return a
def LCD(a, b):
lcd = GCD(a, b)
return a*b//lcd
T = int(input())
for i in range(T):
a, b = map(int, input().split())
print(LCD(a, b))
4. GCD 합 9613
- 양의 정수 n개가 중졌을 때, 가능한 모든 쌍의 GCD의 합을 구한다.
- 첫 번째 줄에는 테스트 케이스의 개수 t이 주어진다.
- 다음에는 n개의 수가 주어진다.
모든 쌍을 어떤 식으로 나타낼 것인가? 4 10 20 30 40이 들어온다고 한다면 10 20 / 10 30 / 10 40 -> 3가지 20 30 /20 40/ -> 2가지 30 40 -> 1가지 for문을 2번 도는 것으로 문제 해결 가능.
def GCD(a, b): # greatest common divisor
while b:
t = a % b
a, b = b, t
return a
T = int(input())
for i in range(T):
arr = list(map(int, input().split()))
N = arr.pop(0)
result = 0
for i in range(N):
for j in range(i+1, N):
result += GCD(arr[i], arr[j])
print(result)
고려해야 할 사항
- for문의 구성
# N = 4라면
for i in range(N):
for j in range(i+1, N):
print(i,j) # 0 1 0 2 0 3 / 1 2 1 3 / 2 3
- 리스트의 값 삭제와 반환을 동시에 해줄 순 없을까? -> pop method
5. 소수 찾기 1978
- 에라토스테네스의 체 사용
- 입력 값은 array의 max 값을 구한다 (n이라고 하자)
- range(2,n)을 통해, 2부터 n까지의 list를 구한다.
- n // 0.5를 통해 제곱근을 구한뒤, 그 제곱근 까지의 소수를 빼준다.
- 소수를 구했으니 for문을 돌면서 소수 체크후 리턴
T = int(input())
arr = list(map(int, input().split()))
n = max(arr)
prime = set(range(2, n+1))
for i in range(2, int(n**0.5)+1):
prime -= set(range(i*2, n+1, i))
result = 0
for i in arr:
if i in prime:
result += 1
print(result)
복습
- 제곱근을 구하기 위해서는
int(n**0.5)+1를 사용할 수 있다. - range(시작수, 끝나는 수, 증가하는 수) , range의 2번째 인자에 n+1을 넣는 것을 주의하자
6. 골드바흐의 추측
- 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
- 예를 들어 8은 3+5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다.
- 20 = 3 + 17 , 42 = 5+37 = 11+31 = 13 +29이다.
-
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램 작성
- 입력
- 각 테스트 케이스는 짝수 정수 n 하나로 이루어진다. (테스트 케이스는 10만개를 넘지 않는다.)
-
입력의 마지막 줄에는 0이 하나 주어진다.
- 출력
- n = a + b 형태로 출력. (n을 만들 수 있는 방버이 여러가지라면 b-a가 가장 큰 것을 출력)
- 두 홀수의 소수의 합으로 나타낼 수 없는 겨우 “Goldbach’s conjecture is wrong”을 출력
- 소수를 구한다
- n(테스트 케이스로 입력 받은 짝수)보다 작은 소수의 리스트를 구한 뒤, (정렬?)그 뒤 n에서 가장 큰 수에서 n을 뺀 수가 소수의 리스트에 있는지 확인, 없으면 순차적으로 그 다음 큰 수를 찾아서 계산
- 시간초과
while(True):
n = int(input())
if n == 0:
break
prime = set(range(2, n+1))
for i in range(2, int(n**0.5)+1):
prime -= set(range(i*2, n+1, i))
prime = list(prime)
# print(prime)
for i in range(len(prime)-1, -1, -1):
if n-prime[i] in prime:
print("%d = %d + %d" % (n, n-prime[i], prime[i]))
break
else:
print("Goldbach's conjecture is wrong.")
-> 미리 에라토스테네스의 체를 통해서 소수를 구해놓고 계산하자.
-> 그런데, 미리 구한다고 하더라도, 그 해당 값을 구한 소수에서 찾으려면 또 for문을 돌아야 한다. -> 이 역시 시간초과
import sys
n = 1000001
prime = set(range(2, n+1))
for i in range(2, int(n**0.5)+1):
prime -= set(range(i*2, n+1, i))
while(True):
n = int(sys.stdin.readline())
if n == 0:
break
prime = list(prime)
for j in range(n):
if prime[j] > n:
break
for i in range(j-1, -1, -1):
if n-prime[i] in prime:
print("%d = %d + %d" % (n, n-prime[i], prime[i]))
break
else:
print("Goldbach's conjecture is wrong.")
- 무엇이 문제인지 모르겠어서 다른 사람 코드를 찾아봤다. 참고한 블로그
- set을 이용해서 찾은게 아니라, prime을 boolean list로 초기화 한 후, 소수인 요소에만, True로 바꿔주고 인덱스만을 이용해서 풀었다.
- 다른 사람을 찾아보니 이분탐색을 사용했다. j-1에 사용할 수도 있겠다.
import sys
MAX = 1000000
prime = [False for _ in range(MAX+1)]
for i in range(2, MAX+1):
if i * i > MAX:
break
if prime[i] is False:
for j in range(i*i, MAX+1, i):
prime[j] = True
while(True):
n = int(sys.stdin.readline())
if n is 0:
break
for i in range(2, MAX+1):
if prime[i] is False:
j = n - i
if prime[j] is False:
print(n, "=", i, "+", j)
break
else:
print("Goldbach's conjecture is wrong.")
배운 것
- 짝수인 소수가 2를 제외하고 있을까? -> 2를 제외한 모든 짝수는 소수다.
- 이를 통해 문제를 바꿔 말하면 4보다 큰 모든 짝수를 소수의 합으로 나타낼 수 있는지 판별
- 미리 에라토스테네스의 체를 통해서 값을 구해 놓는다면, 해당 값보다 작은 수로 슬라이스를 어떻게 해주지 ? -> 적어도 범위는 한정해 줄 수 있다.
- 똑같은 방식으로 풀어도 c++에서는 통과되고 파이썬에서는 통과되지 않을 수 있다.
- 그럴 때, 인덱스만을 활용하여 False와 True의 배열을 사용해보자. => set을 굳이 활용하지 않아도 된다는 점
- 개인적으로 6588 보다 더 간단한 9020만 풀었더라도, 만족했을 것 같다. 9020에서는 시간 초과가 안날 것이다.
※ 골드바흐의 추측(9020)
- 두 소수의 차이가 가장 작은 것을 구하고 출력값의 형태가 그 두개만 출력한다는 것 외에는 똑같은 문제.
-
시간제한이 널럴하기 때문에, 그냥 초기 코드로 했어도 통과했을 문제
- 9020 풀이 (코드가 깔끔해서 가져와봤다.)
- 참고블로그
m = 10000
s = [0, 0] + [1]*(m-1)
for i in range(2, int(m**0.5)+1):
for j in range(i+i, m+1, i):
if s[i]:
s[j] = 0
for _ in range(int(input())):
n = int(input())
r = [(x, n-x) for x, y in enumerate(s[:n//2+1]) if y and s[n-x]][-1]
print(r[0], r[1])
소수 찾기 BOJ 1929
-
이 문제 꽤나 헤맸다.
MAX = 1000000
prime = [False for _ in range(MAX+1)]
prime[1] = True
for i in range(2, MAX+1):
if i*i > MAX:
break
if prime[i] is False:
for j in range(i*i, MAX+1, i):
prime[j] = True
m, n = map(int, input().split())
for i in range(m, n+1):
if prime[i] is False:
print(i)
- 아래 해답의 반례를 못찾겠다.
- 아래 set을 이용한 방법보다, 위에서 인덱스를 통해 소수를 찾고 prime 리스트를 통해 소수를 구하는 방법이 훨씬 빠르다.
- 위를 기어가도록하자
- 아래 코드가 채점이 안되서 계속 찾았는데 pypy로 하니까 통과한다. 왜일까.
- 답은 sorted함수를 추가해주지 않아서이다.
- python3에서는 집합일 때는 sorted를 빼지말자
M, N = map(int, input().split())
if M == 1:
M = 2
prime = set(range(M, N+1))
for i in range(2, int(N**0.5)+1):
prime -= set(range(i*2, N+1, i))
for i in sorted(prime):
print(i)
참고자료 [BOJ문제]https://www.acmicpc.net/problem/15649