백준 알고리즘 8단계 (에라토스테네스의 체)

• 새롭게 배운 내용

1) 1978번 소수 찾기

먼저 소수의 규칙성에 대해 구글링 해봤으나, 완벽한 규칙성은 아직까지도 존재하지 않는다고 한다.
따라서 입력될 값은 1000이하이기에 런타임에러가 나지 않는다면, 입력값보다 작은 정수들로 나누어 떨어지지 않는 경우를 소수로 판별했다.

N = int(input())
nums = list(map(int, input().split()))
cnt = 0

for num in nums:
    cnt += 1
    if num > 2:
        for i in range(2, num):
            if num % i == 0:
                cnt -= 1
                break
    # 단 1, 2는 별도로 판단했다.
    elif num == 1:
        cnt -= 1
    elif num == 2:
        continue

print(cnt)

2) 2581번 소수 판별

방식은 위와 동일하다.

N = int(input())
M = int(input())
ansList = list()

for i in range(N, M+1):
    if i == 2:
        ansList.append(2)
    else:
        for r in range(2,i):
            if i % r == 0:
                break
            if r == i-1:
                ansList.append(i)

if len(ansList) != 0:
    print(sum(ansList))
    print(min(ansList))
else:
    print(-1)

3) 11653번 소인수분해

제출해서 정답처리 될 때 까지 너무 오랜 시간이 걸린것 같았는데 런타임에러는 나지 않았다..

N = int(input())

i = 2
#입력값이 1이면 무시
if N == 1:
    pass
else:
    while i <= N:
        if N % i == 0:
            print(i)
            N = N / i
        else:
            i += 1

4) 1929번 소수 구하기 (에라토스테네스의 체 알고리즘)

시간초과 문제로 나를 많이 괴롭혔던 문제..!
마지막에 극적으로 이중반복문을 제거하며 답을 얻을 수 있었다.

이를 통해 알게 된 것: 에라토스테네스의 체는 주어진 범위 내 소수를 판별하는 가장 효율적인 방식이라는 것

위 이론에 의하면 소수를 판별하기 위해 n까지 모든 수의 배수를 나눠볼 필요가 없고, n의 제곱급 까지만 나눠봐도 충분하다는 것을 알 수 있다.

이를 활용하여 두번 째 시도를 했으나 이중반복문 때문인지 시간초과에 걸렸고, 반복문을 제거하고 함수를 호출하는 방식으로 변경하여 겨우 정답 코드를 얻을 수 있었다..

참고: https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

# 시간 초과 난 제출 코드...!
M, N = map(int, input().split())
all_list = list(range(M, N + 1))
k = 2
for i in range(N-M+1):
    if all_list[i] == 0:
        continue
    scope = int(N/k)
    for j in range(2, scope + 1):
        if (j*k) in all_list:
            idx = all_list.index(j*k)
            all_list[idx] = 0
    k += 1

cnt = all_list.count(0)
for t in range(cnt):
    all_list.remove(0)

for u in range(len(all_list)):
    print(all_list[u])

# 시간초과 2.. 반복문의 범위를 제곱근의 크기로 줄였으나 여전히 시간초과
M, N = map(int, input().split())
all_list = list(range(M, N + 1))
ans_list = list()
for i in all_list:
    ans_list.append(i)
    for j in range(2, int(i**0.5)+1):
        if i % j == 0 and i != j:
            ans_list.remove(i)
            break
if 1 in ans_list:
    ans_list.remove(1)
for t in range(len(ans_list)):
    print(ans_list[t])

# 시간 초과를 피하고자 이중 반복문을 제거하고 함수 호출 방식을 택했다.
M, N = map(int, input().split())

def primeCheck(num):
	# 입력값이 1이라면 바로 False 리턴
    if num == 1:
        return False
    # 아닌 경우에는 입력값의 제곱근 + 1만큼만 반복을 돌아 판별
    else:
        for i in range(2, int(num**0.5)+1):
        	# 만약 나누어 떨어진다면 False 리턴
            if num % i == 0:
                return False
        # 모두 나누어 떨어지지 않았다면 True 리턴
        return True

for i in range(M, N+1):
    if primeCheck(i) == True:
        print(i)

5) 4948번 베르트랑 공준

입력된 n과 2n 사이의 값 중 소수가 몇개인지 파악
단, 입력값이 0이 될 때 까지 반복되기에 계속해서 for문을 돌린다면 시간초과!
따라서 주어진 범위를 활용하여 해당 소수 리스트를 저장한다.
소수 리스트 내 입력 범위에 해당하는 element 개수 출력

#소수 체크 함수
def primeCheck(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
#주어진 모든 범위
all_list = list(range(2, 246912))
prime_list = []

#주어진 모든 범위 내 소수만을 담은 리스트 prime_list
for k in all_list:
    if primeCheck(k) == True:
        prime_list.append(k)

#반복문 내부에서는 이미 만들어진 리스트 내부 값으로만 판별한다.
while True:
    n = int(input())
    cnt = 0
    if n == 0:
        break
    for j in prime_list:
        if n < j <= 2*n:
            cnt += 1
    print(cnt)

6) 9020번 골드바흐의 추측

추측: 입력한 짝수의 값은 두 개의 소수 합으로 구성할 수 있다
소수 합 구성 중 차가 가장 작은 것을 출력하라

# 소수 판별 함수
def primeCheck(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
# 입력 받을 수 있는 범위
all_list = list(range(2, 10000))
# 범위 내 소수만을 담을 리스트
prime_list = []

for k in all_list:
    if primeCheck(k) == True:
        prime_list.append(k)

T = int(input())
for _ in range(T):
    n = int(input())
    check_idx = 0
    fir = 0
    for j in prime_list:
        if j >= int(n/2):
        	# 입력 받은 수의 1/2보다 첫번 째로 큰 값을 fir에 담아줌
            fir = j
            check_idx = prime_list.index(fir)
            break
    idx = 1
    while True:
    	# 입력 받은 수에서 fir를 빼주면 sec
        sec = n - fir
        # sec가 소수 리스트에 있다면 조건 성립
        if sec in prime_list:
            if fir > sec:
                print(str(sec) + ' ' + str(fir))
            else:
                print(str(fir) + ' '+ str(sec))
            break
        else:
            fir = prime_list[check_idx - idx]
            idx += 1

7) 1085번 직사각형에서 탈출

x, y, w, h = map(int, input().split())

a = w - x
b = h - y

# 경계선 까지의 4가지 루트 거리를 담은 리스트
ans_list = [x, y, a, b]

print(min(ans_list))

8) 3009번 네 번째 점

x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())
x3, y3 = map(int,input().split())

x_list = [x1, x2, x3]
y_list = [y1, y2, y3]

# 리스트에 중복되지 않은 수가 네번째 점의 좌표값이다!
for i in x_list:
    if x_list.count(i) == 1:
        x4 = i
        break

for j in y_list:
    if y_list.count(j) == 1:
        y4 = j
        break
print(str(x4)+ ' '+ str(y4))

9) 4153번 직각삼각형(피타고라스의 정리)

while True:
    a, b, c = map(int, input().split())
    if a == b == c == 0:
        break

    check_list = [a, b, c]
    # 가장 큰 element를 따로 저장하고 리스트에서 제거
    maxElement = max(check_list)
    check_list.remove(maxElement)
	
    #이를 활용하여 피타고라스 정리 (a^2 + b^2 = c^2)
    if (maxElement ** 2) == (check_list[0] ** 2) + (check_list[1] ** 2):
        print('right')
    else:
        print('wrong')

10) 3053번 택시 기하학

택시 기하학에서 두점(T1(x1,y1), T2(x2,y2)) 사이의 거리인 D는
D(T1,T2) = ㅣx1 - x2ㅣ + ㅣx2 - y2ㅣ 로 정의된다.

따라서 택시 가하학에서의 원은 아래와 같이 다이아몬드 모양의 정사각형이 되며 넓이는
2 * R^2 이 된다. (정사각형의 넓이)

출처: https://ahdelron.tistory.com/m/41

import math

R = int(input())
uclid = R**2 * math.pi
taxi = 2 * (R**2)

print(f'{uclid:.6f}')
print(f'{taxi:.6f}')

11) 1002번 터렛

두 원의 원점 좌표와 반지름의 길이를 입력하여 두 원의 위치관계를 묻는 문제이다. 따라서 원점간 거리와 반지름의 합 차로 판별하는 조건문을 작성

T = int(input())

for i in range(T):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    # 만약 두 사람의 좌표와 반지름이 길이가 같다면 류재명 위치의 개수는 무한대
    if x1 == x2 and y1 == y2 and r1 == r2:
        print(-1)
        # 다음 케이스로 넘어가기 break는 반복문 아예 종료
        continue
    # 원 간의 위치관계 ( d는 두 사람간 거리)
    d = (((x1 - x2) ** 2) + ((y1 - y2) ** 2)) ** 0.5
    if r1 + r2 == d:
        print(1)
    elif r1 + r2 < d:
        print(0)
    # 어떤 값이 더 큰지 모르니 절댓값 처리 abs()
    elif abs(r1 - r2) < d < r1 + r2:
        print(2)
    elif abs(r1 - r2) == d:
        print(1)
    elif abs(r1 - r2) > d:
        print(0)