항해99 TIL [12/7]

이지연·2021년 12월 8일
0

항해99 TIL

목록 보기
25/33
post-thumbnail

알고리즘 주간 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)
    
profile
개발하는 디자이너입니다.

0개의 댓글