[백준] 수학_4948, 15649, 2609, 9020, 11653, 6588, 1182, 6603

베르트랑 공준

• 코드

import math

arr = []
while True:
    n = int(input())
    if n==0:
        break
    arr.append(n)

# 입력 받은 값 중 가장 큰 값까지 에라토스테네스의 채로 소수 확인
arr_max = max(arr) 

temp = [0] * ((2*arr_max)+1)

for i in range(2, int(math.sqrt(2*arr_max))+1):
    k = 2
    while k * i <=2*arr_max:
        temp[k*i] = 1
        k+=1

for i in range(len(arr)):
    count = 0
    # 입력 받은 값마다 n+1 ~ 2n 범위에서 소수 개수 찾기
    for j in range(arr[i]+1,2*arr[i]+1):
        if temp[j] == 0:
            count+=1
    print(count)

• 풀이를 생각해낸 과정
  • 입력 받은 값 중 가장 큰 값을 기준으로 소수를 찾고, 입력 받은 값마다 입력 받은 값마다 n+1 ~ 2n 범위에서 소수 개수를 찾는다.
• 시간복잡도 계산
  • O(N^2)

N과 M(1)

• 코드

from itertools import permutations
n,m = map(int,input().split())

temp = []
for i in permutations(range(1,n+1),m):
    temp = list(i)
    print(' '.join(str(s) for s in temp))

• 풀이를 생각해낸 과정
  • 파이썬 라이브러리를 활용하여 중복을 허용하지 않고 n개에서 m개를 뽑는다.
  • 출력 포맷을 맞추기 위해 숫자를 문자열로 바꾼뒤, join으로 출력한다.
• 시간복잡도 계산
  • O(N!)

최대공약수와 최소공배수

• 코드

n,m = map(int,input().split())

def gcd(a,b):
    if a < b:
        a, b = b, a
    while a>0:
        b,a = a, b%a
    return b

def lcm(a,b,gcd):
    return int(a*b / gcd)

gcd = gcd(n,m)
print(gcd)
print(lcm(n,m,gcd))

• 풀이를 생각해낸 과정
  • 유클리드 호제법 이용
• 시간복잡도 계산
  • O(N)

골드바흐의 추측

• 코드

import math
n = int(input())

arr = [int(input()) for i in range(n)]

temp = [0] * 10001
temp[0] = 1
temp[1] = 1

for i in range(2, int(math.sqrt(10000))+1):
    k = 2
    while k * i <= 10000:
        temp[k*i] = 1
        k+=1

for i in arr:
    k = int(i/2)
    
    if temp[k] == 0:
        print(k,k)
        
    else:
        for j in range(1,k-1):
            if temp[k-j] == 0 and temp[k+j] == 0:
                print(k-j,k+j)
                break

• 풀이를 생각해낸 과정
  • 10000 까지 소수 확인 리스트를 구한 뒤,
  • 입력받은 값이 2로 나누었을 때 홀수이면 바로 출력 , 아니라면 반으로 나눈 값을 기준으로 +1, -1 한 값이 모두 홀수라면 출력
  • ex ) 0 1 2 3 4 5 6 7 8 이라면 4를 기준으로 대칭 합이 8이다.
• 시간복잡도 계산
  • O(N^2)

소인수분해

• 코드

n = int(input())

if n == 1:
    print("")

def factorization(x):
    d = 2

    while d <= x:
        if x % d == 0:
            print(d)
            x = x / d
        else:
            d = d + 1

factorization(n)

• 풀이를 생각해낸 과정
  • 소수를 계산한 뒤 푸는 방식을 생각했는데 시간 초과, 소수가 아닌 수로 나누어지는 점을 우려했는데 숫자를 하나씩 늘려나가는 방식으로 가능
• 시간복잡도 계산
  • O(N)

골드바흐의 추측

• 코드

from sys import stdin

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

while True:
    n = int(stdin.readline())

    if n == 0: break

    for i in range(3, len(array)):
        if array[i] and array[n-i]:
            print(n, "=", i, "+", n-i)
            break

• 풀이를 생각해낸 과정
• 시간복잡도 계산
• 코드
  • 왜 런타임 에러 나는지 모르겠음

import math
temp = [0] * 100001
temp[0] = 1
temp[1] = 1
for i in range(2, int(math.sqrt(100000))+1):
    k = 2
    while i * k <= 100000:
        temp[i*k] = 1
        k+=1

while True:
    n = int(input())
    if n == 0:
        break
    for i in range(1,n):
        if i == n:
            print("Goldbach's conjecture is wrong.")
            break
                
        if temp[i] == 0 and temp[n-i] == 0:
            print(f"{n} = {i} + {n-i} ")
            break

• 풀이를 생각해낸 과정
  • 에라토스테네스 채
• 시간복잡도 계산

부분수열의 합

• 코드

from itertools import combinations

n, s = map(int,input().split())
arr = list(map(int,input().split()))
count = 0

for i in range(1,n+1):
    temp = []
    temp = list(combinations(arr, i))
    for j in temp:
        if sum(j) == s:
            count +=1
print(count)

• 풀이를 생각해낸 과정
  • 조합 라이브러리
• 시간복잡도 계산
  • 조합 시간 복잡도 ..?
• 코드

n, s = map(int,input().split())
arr = list(map(int,input().split()))
count = 0

def dfs(idx, temp, k):
    if len(temp) == k:
        answer.append(temp[:])
        return

    for i in range(idx, n):       
        dfs(i+1,temp+[arr[i]],k)

for i in range(1, n+1):
    answer = []
    dfs(0, [],i)
    for j in answer:
        if sum(j) == s:
            count+=1
print(count)

• 풀이를 생각해낸 과정
  • dfs 로 조합 구현
• 시간복잡도 계산
  • O(N^2)
• 참고

temp = [1] 
print(temp + [1]) #[1, 1] 
temp = [[1],[1]] 
print(temp + [1]) #[[1], [1], 1]

로또

• 코드

from itertools import combinations
while True:
    arr = list(map(int,input().split()))
    if arr[0] == 0:
        break
    for i in combinations(arr[1:],6):
        print(' '.join(map(str,list(i)))) # == print(' '.join(str(s) for s in list(i)))
    print()

• 풀이를 생각해낸 과정
  • 조합 라이브러리
  • 출력 형태 맞추기 위해 join 함수 이용
• 시간복잡도 계산
  • 조합 라이브러리 시간 복잡도..?
• 코드

def combination(idx, temp):
    if len(temp) == 6:
        answer.append(temp[:])
        return
    for i in range(idx, arr[0]):
        combination(i+1,temp+[arr[i+1]])
    
while True:
    answer = []
    arr = list(map(int,input().split()))
    if arr[0] == 0:
        break
    combination(0,[])
    print(answer)
    for i in answer:
        print(" ".join(map(str,i)))
    print()

• dfs로 조합 구현
• O(N^2)
• 참고 : print(”\n”) → 2줄 출력 , print() → 1줄 출력