백준 알고리즘 약수, 소수와 배수 2 (2)

오랜만에 알고리즘 푸니까 안풀린다.. 역시 매일매일 해야한다. 

17103 골드바흐 파티션

골드바흐 파티션

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초

512 MB

36315

13308

10242

34.562%

문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력

 

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

예제 입력 1 복사

5
6
8
10
12
100

예제 출력 1 복사

1
1
2
1
6

 

로직 정리

1. T의 컨디션을 구한다 

2. 계산할 짝수 n을 주고, n에 해당하는 소수를 구하게 한다. 

3. 소수끼리 더해서 n이랑 같은 소수의 조합을 combination을 통해 숫자를 구한다 

 

초기 코드

import sys
t = int(sys.stdin.readline())
x = []
a_list = []
def soe(z):
    primes = [True] * (z+1)
    primes[0] = primes[1] = False
    for i in range(2, int(z**0.5) + 1):
        if primes[i] :
            for j in range(i*i, n+1, i):
                primes[j] = False

                
for n in range T : 
    if n % 2 == 0:
        x.append[n] = soe(n)
        for i in range x :
            for j in range x[i+1]:
                if i + j == n:
                  a_list.append(i,j)

print(math.comb(len(a_list),2))

2개씩 묶은 소수의 컴비네이션의 갯수를 구하려 했음 

 

개선 코드 

import sys

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    return primes

def count_goldbach_partitions(n, primes):
    count = 0
    for i in range(2, n//2 + 1):
        if primes[i] and primes[n-i]:
            count += 1
    return count

max_n = 1000000
primes = sieve_of_eratosthenes(max_n)

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    print(count_goldbach_partitions(n, primes))

 

1. 에라스토테네스의 체를 이용해 주어진 N까지의 모든 소수를 찾기

2. 불리언 리스트를 사용하여 각 숫자가 소수인지 아닌지를 표시

3. √n까지만 반복하여 효율성 을 높임

 

골드바흐 파이션 카운트 함수 

 

13909번

창문 닫기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

64 MB

18087

9056

8022

50.128%

문제

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

마지막에 열려 있는 창문의 개수를 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

1

예제 입력 2 복사

24

예제 출력 2 복사

4

 

1. 에라스토테네스의 채를 이용하여 n까지의 소수의 갯수를 구하는 문제와 같은데, 1을 포함하는 소수의 갯수

 

초기 코드 

 

import sys
def seo(n):
    primes = [True] * (n+1)
    primes[0] = False
    for i in range(2, int(n**0.5)+1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    return primes

max_n = 2100000000

n = int(sys.stdin.readline())
for _ in range(n):
    print(seo(n))

 

메모리 초과됨

n값이 너무 크면 안되는 것 같음. 

 

인줄 알았으나, n번째 창분이 열려있으려면, n의 약수의 개수가 홀수여야한다는 사실을 잊지 말아야함. = 완전제곱수

math 함수를 내장함수로 사용할 수 있음

import math

N = int(input())
result = int(math.sqrt(N))
print(result)

int(math.sqrt(N)) 는 n까지의 제곱근의 수를 정수로 구함 

 

못푼 문제 :

4134번 다음 소수 

다음 소수 실패다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

40996

10909

8692

25.022%

문제

정수 n(0 ≤ n ≤ 4*10^9)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

3
6
20
100

예제 출력 1 복사

7
23
101

 

에라토스테네스의 채를 쓰되, 범위가 넓기 때문에 n부터 시작해 가장 작은 소수를 찾으면 멈추어야 할 것 같음

--> 메모리 이슈 발생

에라토스테네스의 채는 소수의 갯수를 나타냄. 

1. n이 2 또는 3이면 그 수 자체가 답입니다.
2. n이 2나 3보다 크다면:
   a. n이 짝수라면 n+1부터 시작합니다. (짝수는 2를 제외하고 소수가 될 수 없으므로)
   b. n이 홀수라면 n부터 시작합니다.
3. 시작 수부터 6k±1 형태의 수로 검사를 진행합니다:
   • i = 5부터 시작 (5는 6k-1 형태의 첫 수)
   • 매 반복마다 i += 2, i += 4를 번갈아 수행하여 6k±1 형태의 수를 생성
4. 각 i에 대해:
   • √n까지만 검사
   • n이 i로 나누어 떨어지면 소수가 아님
   • 나누어 떨어지지 않으면 다음 i로 진행
5. 모든 검사를 통과하면 그 수가 소수입니다.

import sys

t int(sys.stdin.readline())
for _ in range t:
    n= int(sys.stdin.readline())
    if n == 2 or n == 3 :
        result == n
    elif n > 3 :
        for i in range(5, n**0.5, 2)
            if i // n == 0:
                result = i
print(result)

 

초기 코드와 정답 코드 

import sys

def is_prime(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0: #2와3의배수제외
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6  #6씩증가시키면서6K-1과 6k+1 형태의 수를 모두 검사함 
    return True

def next_prime(n):
    if n <= 2:
        return 2
    if n % 2 == 0: #2로 나눠지는애면 1씩더해
        n += 1
    while True:
        if is_prime(n): #그게 소수이면 n값으로 가져옴 
            return n
        n += 2

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    result = next_prime(n)
    print(result)

 

is prime 함수로 소수를 판별하고, next_prime 함수로 가장 작은 소수를 찾고 6+-1형태의 수를 효율적으로 검사

간단한 로직인데, 아직까지고 코드화시키는걸 어려워한다. 

매일 조금씩이라도 고민하면서 풀어나가자