[백준] 9020번(골드바흐의 추측)

백준 9020번

처음 제출한 코드

repeat = int(input())
for k in range(repeat):

  n = int(input())
  num_list = []
  # 1은 소수가 아님. 자기 자신은 소수여도 자연수의 합으로 이루어져야 하기 때문에 해당 안함
  for i in range(2, n):
    check = True
    for j in range(2, i):
      if i%j==0:
        check = False
        break
    if check == True:
      num_list.append(i)
  
  i=0
  number = 0
  while num_list[i] <= int(n*0.5):
    if (n-num_list[i]) in num_list:
      number = num_list[i]
    i+=1
  
  print(number,n-number)

• 시간초과

수정한 코드

k = 10001
prime_list = [1]*k
prime_list[0], prime_list[1]= 0,0

# <에라토스테네스의 체> 알고리즘
for i in range(2, int(math.sqrt(k))+1):
  for j in range(i*2, k, i):
    prime_list[j]=0


repeat = int(input())

for j in range(repeat):
  
  n = int(input())
  result = 0

  for i in range(2, n//2+1):
    if (prime_list[i]==1) and (prime_list[n-i]==1):
      result = i
  print(result, n-result)

• 런타임 에러

• 다른 사람이 작성한 코드를 참고하여 작성
• 범위 내의 모든 수가 소수인지 아닌지를 검사하는 방법으로는 시간 초과 발생
  => <에라토스테네스의 체>라는 소수 찾기 알고리즘을 활용

최종 제출 코드

import math

k = 10001
prime_list = [1]*k
prime_list[0], prime_list[1]= 0,0

for i in range(2, int(math.sqrt(k))+1):
  # 추가한 코드
  if prime_list[i]==1:
    for j in range(i*2, k, i):
      prime_list[j]=0

repeat = int(input())

for j in range(repeat): 
  n = int(input())
  result = 0

  for i in range(2, n//2+1):
    if (prime_list[i]==1) and (prime_list[n-i]==1):
      result = i
  print(result, n-result)

• 런타임 에러의 원인으로는 아래와 같은 것들이 있다
  1) 배열의 할당된 크기를 넘어서 접근했을 때
  2) 자료형을 넘어가는 값을 받았을 때 (int형 => long long형)
  3) 무한루프를 돌 때
  4) 0으로 나눌 때 (a = b/0)
  5) 할당이 해제된 메모리를 참조할 때
  6) 재귀 호출이 너무 깊어질 때
  7) 메모리 제한을 넘어갈 때
  [출처]

• 1) or 3) 중에 하나가 원인이라고 판단
• 1): 리스트 범위를 벗어난 접근 없음 => (X)
• 3): 무한루프는 아니지만 prime_list의 원소값을 변경해주는 코드에서 많은 횟수의 루프 발생
  ◻ 이미 소수가 아님이 판명되어 리스트 원소의 값이 바뀌어 있는 경우는 그 소수의 배수들도 원소의 값이 바뀌어 있음
  ex) 4는 2의 배수이기 때문에 i=4가 되기 전에 prime_list[4]의 값이 1로 업데이트 되어 있다
  => 모든 4의 배수는 2의 배수이기 때문에 이미 리스트 값이 업데이트 되어 있음
  ✔ if prime_list[i]==1: 코드를 추가하여 반복횟수 줄임 (O)