1부터 n 까지 연속한 숫자의 합을 구하는 알고리즘

안녕하세요, 츄르 사려고 코딩하는 집사!      코집사입니다.

---

1. 1부터 n 까지 연속한 숫자의 합을 구하는 알고리즘

---

1부터 n 까지 연속한 숫자의 합을 구하는 알고리즘은 여러가지 방법이 있다.

 

1) for 문을 이용한 숫자의 합 구하기

2) 가우스를 이용한 합

 

1번은 for문을 이용하여 쉽게 구할 수 있다.

2번은 가우스 공식인 n(n+1) / 2 를 사용하면 구할 수 있다. 아래의 코드처럼 말이다.

 

n = int(input())

def Sum_Number(n) :
    return n*(n+1) // 2
    
print(Sum_Number(n))

 

시간 복잡도를 보면, 1번 같은 경우는 O(n)이라고 할 수 있습니다. 1부터 n까지의 합을 for문으로 사용할 경우 n번을 더해야 구할 수 있습니다.

하지만, 2번은 곱셈과 덧셈, 나눗셈 총 3번을 연산하기 때문에 큰 숫자에선 확실히 2번이 더 빠릅니다.

 

---

2. 1부터 n 까지 연속한 숫자 제곱의 합을 구하는 알고리즘

---

1부터 n까지 연속한 숫자 제곱의 합도 for문을 이용하여 구할 수 있고, 공식을 이용하여 구할 수 있습니다.

 

공식은 n*(n+1)*(2*n+1) / 6 으로 구할 수 있습니다.

 

n = int(input())

def Sum_Number(n) :
    return n*(n+1)*(2*n+1) // 6
    
print(Sum_Number(n))