알고리즘 주간 2일차, 오늘도 어제와 크게 다른 것 없이 주어진 알고리즘 인강으로 학습을 하며 백준 사이트에서 또다른 알고리즘 문제를 학습해보는 시간을 가져보았다. 사실 알고리즘 문제를 푸려고 할 때마다 수학문제의 연장선 같기도 하고 감이 오지 않는 경우가 아직까지는 대부분이다. 하지만 첫 술에 배부를 수는 없는 법이니, 일종의 문제해결력을 기른다는 생각을 하며 참을성을 가지고 이어나가 보려고 한다.
단계별 해결법
해답을 도출하기 위해서는 먼저 소수를 구하는 방법을 알아햐 함.
링크 : https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)
이번 문제에서 까다로웠던 부분은 "시간 초과". 결과를 도출하는 것까지 수행을 완료했지만 cpu 부담을 최대한 낮추어 경량화할 수 있는 코드가 필요했음. 처음에 진행한 코드는 배열에 소수들을 미리 저장시키지 않고서 즉각적인 계산을 수행하도록 했지만,정답이 된 코드는 소수들을 미리 구하여 리스트나 튜플에 저장시킨 후 값들을 찾아내야 했음.
처음에는 소수들을 저장하는 리스트 만드는 시간이 더 오래 걸릴 것 같다는 생각을 했지만, 좀 더 생각해봤을 때 주어진 값만 입력하는 것이 아니라 더욱 다양한 값들을 입력했을 경우에는 즉각적인 연산 방식이 cpu를 기하급수적으로 많이 사용하는 결과를 가져온다는 것.
정답 코드
import math
# 소수인지를 판별하는 함수
def checkValue(numValue):
if numValue == 1:
return True
else:
for comp in range(2, int(math.sqrt(number))+1):
if numValue % comp == 0:
return False
return True
# 소수를 리스트에 저장
value = list(range(123456*2))
prime_number = list()
for number in value:
if checkValue(number):
prime_number.append(number)
# 사용자 입력 및 결과 출력
while(1):
insertN = int(input())
cnt = 0
if insertN == 0:
break
for valueN in prime_number:
if insertN < valueN <= insertN*2:
cnt += 1
print(cnt)
시간 초과 코드
import math
# 소수를 판별하는 함수
def checkValue(numValue):
if numValue == 1:
return True
else:
for comp in range(2, int(math.sqrt(number))+1):
if numValue % comp == 0:
return False
return True
# 사용자 입력 및 출력 부분
while(1):
insertN = int(input())
prime_number = 0
if insertN == 0:
break
else:
for number in range(insertN+1, insertN*2+1):
if checkValue(number):
prime_number += 1
print(prime_number)