[ 알고리즘 ] 1부터 n까지 숫자의 합 구하기, 1~100 / 1~1000 까지 숫자의 합 구하기, 알고리즘에 따라 걸리는 시간

[ 들어가며 ]

 

1부터 n까지 숫자의 합을 구하는 방법은

여러 가지가 있을 수 있겠지만,

1부터 n까지 숫자를 하나씩 더하는 방법과,

수학 공식을 사용하여 계산하는 방법이 있을 수 있습니다.

 

오늘은 1부터 n까지 더하는 방법에 대해 알아보고

어떤 방법이 더 효율적인지

확인해 보겠습니다.

 

[ 알고리즘 ]

 

첫 번째.  1부터 n까지 숫자를 하나씩 더하기

def total_sum(n):
    total = 0
    for i in range(1, n+1):
        total = total + i
    return total
    
result = total_sum(100)

print(result)

 

두 번째.  수학공식을 사용한 계산

def total_sum(n):
    return n*(n+1)//2

result = total_sum(1000)
print(result)

 

참고로 [ // ]는 나눗셈 결과를 정수로만 보여주게 합니다.

[ / ]를 사용하면 [ 500500.0 ] 이런 식으로 결과가 나타납니다.

728x90

반응형

[ 시간측정하기 ]

 

시간을 측정하기 위해서

[ time 모듈 ]을 사용합니다.

최종시간에서 시작시간을 빼서

걸린 시간을 측정합니다.

 

먼저 1부터 n까지 숫자를 하나씩 더한 알고리즘의 시간을 측정해 보겠습니다.

작은 숫자를 정하면 시간 측정이 안되므로

충분히 큰 숫자로 검증을 하면 됩니다.

import time

def total_sum(n):
    total = 0
    for i in range(1, n+1):
        total = total + i
    return total

start = time.time()  
result = total_sum(99999999)
end = time.time()

print(result)
print(f"걸린시간 : {end-start : .6f}" )

이렇게 하면

합계는 4999999950000000이며,

걸린 시간은 5.013607초입니다.

 

다음은 수학 공식을 사용한 알고리즘의 시간을 측정해 보겠습니다.

import time

def total_sum(n):
    return n*(n+1)//2

start = time.time()  
result = total_sum(99999999)
end = time.time()

print(result)
print(f"걸린시간 : {end-start : .6f}" )

합계는 동일하게  4999999950000000 이지만,

걸린 시간은 0.000000초로 출력이 됩니다.

 

걸린 시간은 시스템마다 다를 수 있지만,

수학 공식을 사용하였을 경우에는

소수점 6자리까지 시간을 표시해도

측정되지 않았습니다.

 

수학공식을 사용했을 때에는

숫자를 어느 정도 더 키워도 시간이 측정되지 않았습니다.

 

이렇게 사용하는 알고리즘에 따라

프로그램의 실행시간이 차이가 나게 됩니다.