[Python-Baekjoon] 기본수학 2

백준-단계별로 풀어보기-'기본 수학 2' 파트 문제들 중 기억해야 할 개념 및 문제들을 기록합니다.

2022.01.17

[Baekjoon] 1978. 소수찾기

:2부터 X-1까지 모두 나눠서 X가 소수인지 판별하는 문제 1

📘 1978 문제 링크

n = int(input())
num_list = list(map(int, input().split()))

cnt = 0

for i in num_list:
    if i != 1:  # 1은 소수 아님
        for j in range(2, i):  # range: 2 ~ i-1
            if i % j == 0:  # 소수 아닌 경우
                break
        else:  # i가 1과 자신 i를 제외한 어떠한 j로도 나눠지지 않는 경우 = 소수
            cnt += 1
print(cnt)

---

2022.01.17

[Baekjoon] 2581. 소수

:2부터 X-1까지 모두 나눠서 X가 소수인지 판별하는 문제 2

📘 2581 문제 링크

m = int(input())
n = int(input())

arr = []  # 빈 배열

for i in range(m, n+1):  # range: m ~ n
    if i == 1:  # 1은 소수 아님
        pass
    elif i == 2:  # 2는 소수임
        arr.append(i)
    else:
        for j in range(2, i):  # range: 2 ~ i-1
            if i % j == 0:  # 무언가로 나눠지는 i는 소수가 아님
                break
            elif j == i-1:  # j가 범위 끝인 i-1까지 도달했다면
                arr.append(i)  # i를 소수 배열에 추가

if len(arr) == 0:
    print('-1')
else:
    print(sum(arr))
    print(min(arr))

---

2022.01.17

[Baekjoon] 11653. 소인수분해

:N을 소인수분해하는 문제

📘 11653 문제 링크

n = int(input())

while n != 1:  # n이 1이 될 때 까지 반복
    for i in range(2, n+1):  # 범위: 2 ~ n
        if(n % i == 0):  # n을 2부터 순차적으로 나누기
            print(i)  # n이 나머지 없이 나눠지면 출력
            n = n // i
            break

---

2022.01.20

[Baekjoon] 1929. 소수 구하기

:에라토스테네스의 체로 풀어 봅시다.

📘 1929 문제 링크

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

for i in range(m, n+1):
    if i == 1:
        continue
    for j in range(2, int(i ** 0.5)+1):  # range(2, i) -> 시간초과 뜸.
        if i % j == 0:
            break
    else:
        print(i)

• 이렇게 풀었을 경우에 맞긴 하지만 시간이 너무 오래걸린다😢 (5840ms)

-->

➰ 그래서 '에라토스테네스의 체'를 활용하여 문제를 풀면 시간이 많이 단축된다. (260ms)

에라토스테네스의 체

: 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법.
소수를 구해야 하는 구간의 수(m~n) 가운데 n의 제곱근보다 작은 소수의 배수를 지우고 남는 수는 모두 소수가 됨.
예를 들어 가장 작은 소수인 2부터 시작해서, 2의 배수(2, 4, 6 ...)를 모두 지우고, 지워지지 않은 남은 수 중에서 다음 소수인 3의 배수(3, 9, 15 ...)를 지움 -> 범위 내에서 계속 반복해 나가면 소수만 남음.

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


def isprime(m, n):
    n += 1
    prime = [True] * n   # 초기화: n개 요소에 True 설정(소수로 간주)

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    for i in range(2, int(n**0.5)+1):
        if prime[i]:   # i가 소수인 경우
            for j in range(2*i, n, i):   # i 이후 i의 배수들을 False 판정
                prime[j] = False

    for i in range(m, n):
        if i > 1 and prime[i] == True:
            print(i)


isprime(m, n)

---

2022.01.21

[Baekjoon] 4948. 베르트랑 공준

:소수 응용 문제 1

📘 4948 문제 링크

def sosu(num):
    if num == 1:
        return False

    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True


# 문제에서 제한한 범위: n <= 123,456 -> 최대를 범위를 2n <= 246,912로 미리 계산
sosu_range = list(range(2, 246912))
sosu_list = []   # 소수담을 빈 리스트

for i in sosu_range:   # 2 <= n <= 246,912
    if sosu(i):   # 소수에 해당하면 소수 리스트에 추가
        sosu_list.append(i)

while(1):
    cnt = 0
    n = int(input())

    if n == 0:   # 0 입력시 입력 종료
        break

    for i in sosu_list:
        if n < i <= 2*n:   # 소수를 담은 리스트가 범위 내에 있으면 카운트
            cnt += 1

    print(cnt)

• 전에 소수 구하는 방식으로 비슷하게 푸니까 계속 시간 초과가 떴다.😢

시간초과 문제를 해결하기 위해 n의 최대 범위를 미리 계산하여 지정해주었다.
또한, 소수를 구하는 함수를 따로 만들었고, 빈 리스트를 선언하여 소수로 판단했을 때 마다 빈 리스트에 값을 추가해주고 이를 카운트해주었다.

---

2022.01.24

[Baekjoon] 9020. 골드바흐의 추측

:소수 응용 문제 2

📘 9020 문제 링크

import sys

def sosu(num):
    for i in range(2, int(pow(num, 0.5)) + 1):  # pow(num, 0.5) = num**0.5
        if num % i == 0:  # 소수가 아닌 경우
            return False
    if num == 1:  # 1은 항상 소수가 아님
        return False
    return True  # 위의 경우 외에는 소수라고 판단

T = int(sys.stdin.readline())

for i in range(T):
    n = int(sys.stdin.readline())
    for num in range(n // 2, 0, -1):  # n//2 ~ 0 까지, -1씩 작아지도록
        if sosu(num) and sosu(n-num):
            print(num, n-num)
            break

값 입력받을 때 int(input()) 보다 int(sys.stdin.readline() 사용하는게 시간 3배정도 더 단축됨.

• pow(): pow(num, 0.5) = num**0.5 즉, 제곱을 표현할 때 사용하는 함수.

---