1. 1부터 n까지의 합 구하기

* 책: 모두의 알고리즘 with 파이썬

 

1. 1부터 n까지의 합을 구하는 방법

• 머릿속에 무의식 중으로 떠오르는 방법은 아래 코드의 방법 1
• 가우스처럼 똑똑하게 천재처럼 구하려면 방법 2 

# 1부터 n까지의 합 구하기 방법1
# 냅다 1부터 더하는 방법
 
def sum_n(n):
    s = 0 # 초기화
    for i in range(1, n+1):
        s = s + i
    
    return s
    
print(sum_n(10)) # 55
 
 
 
# 1부터 n까지의 합 구하기 방법2
# 가우스처럼 똑똑하게 구하기 (난 안됨 ㅠ)
 
def gaus(n):
    return n*(n+1)//2
 
gaus(10) # 55
 
# n*(n+1)에서 '*' 이거 안해주면 TypeError: 'int' object is not callable 오류남
# // 나누기: int return, / 나누기: float return

2. 입력 크기와 계산 횟수 

• 방법 1: 반복문을 사용하는 것이므로 덧셈이 n번 반복되어 사용되는 셈 (총 n번)
• 방법2: n이 아무리 크더라도 덧셈 한번, 곱셈 한번, 나눗셈 한번이면 끝남 (총 3번)

보통 컴퓨터에서 사용하는 연산은 매우매우매우매우 큰 수를 다루므로 방법2처럼 간단하게 짜는 것이 중요

 

3. 대문자 O 표기법: 계산 복잡도(complexity) 표현 '빅 오'

• 방법 1: 사칙 연산을 총 n번 하므로 O(n)으로 표현
• 방법 2: 마치 O(3)일 것 같으나 O(1);
• 입력 크기가 커져도 계산 시간이 더 늘어나지 않는 경우에는 모두 O(1)로 표현 

##################결론#####################
O(n): 필요 계산 횟수가 입력 크기 n과 비례할 때 표기
O(1): 필요 계산횟수가 입력 크기 n과 무관할 때 표기

 

 

<연습 문제>

1부터 n까지 연속한 숫자의 제곱의 합 구하기 

 

# 1부터 n까지의 제곱의 합 구하기 방법 1
# 덧셈과 비슷, O(n)의 방법
 
def sqr_sum(n):
    s = 0
    for i in range(1, n+1):
        s = s + i**2
    
    return s
    
 
# 방법2: {n(n+1)(2n+1)}/6 사용
 
def gaus2(n):
    return n*(n+1)*(2*n+1)//6