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

1부터 n까지의 연속한 정수의 합을 구하는 알고리즘을 만들어보세요.

계산과정
1+2를 계산한 결과인 3을 기억한다
기억해둔 3에 다음 숫자 3을 더해 6을 기억한다.
기억해둔 6에 다음 숫자 4을 더해 10을 기억한다
~ 같은 과정 반복
10까지 더해서 마지막으로 기억된 55를 답으로 제시한다

이 계산과정을 바탕으로 1~n까지의 합을 구하는 알고리즘 과정
-> 1. 합을 기록할 변수 s를 만들고 0을 저장한다.
2. 변수 i를 만들어 1부터 n까지의 숫자를 1씩 증가시키며 반복합니다.
3.[반복블록] 기존의 s에 i를 더하여 얻은 값을 다시 s에 저장합니다.
4. 반복이 끝났을때 s에 저장된 값이 결과값입니다.

def sum_n(n):
    s=0
    for i in range(1,n+1):
        s=s+i
    return s

print(sum_n(10))
print(sum_n(100))

• for i in range i를 1부터n까지 반복

합공식을 이용해구해보기
n*(n+1)/2

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

print(sum_n(10))
print(sum_n(100))

>대문자 O표기법:계산 복잡도 표현(전산학읽고 다시 작성하기)


## 문제
1-1
>1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for반복문으로 만들어보세요(예를 들어 n=10이라면 385를 계산하는 프로그램입니다.
답
```python
def square_sum(a):
    sum=0
    start=1
    for i in range(start,a+1):
        sum+=start**2
        start+=1
    return sum

print(square_sum(10))

답2

def square_sum(a):
    sum=0
    for i in range(1,a+1):
        sum+=i**2
        i+=1
    return sum

print(square_sum(10))

답2가 좀더 효울적 for 문에서 i를 이용할수 있는데 굳이 변수를 따로 만들어 줄 필요 없다.

1-2
연습문제 1-1프로그램의 계산 복잡도는? O(n)

1-3
1부터 n까지 연속한 숫자의 제곱합을 구하는 공식 n(n+1)(2n+1)/6을 이용할수 있다. for반복문 대신 이 공식을 이용하면 알고리즘의 계산 복잡도는? O(1)

def square_sum(a):
    return a*(a+1)*(2*a+1)/6

print(square_sum(10))