UNIT 01 (기초)

1부터 n까지의 합 구하기

문제) 1부터 n까지 연속한 정수의 합을 구하는 알고리즘을 만들어라.

방법1

#1부터 n까지 연속한 숫자의 합을 구하는 알고리즘1
#입력 : n
#출력 : 1부터 n까지의 숫자를 더한 값

def sum_n(n):
    sum = n * (n + 1) / 2

    return sum

print(sum_n(n))

방법2

#1부터 n까지 연속한 숫자의 합을 구하는 알고리즘2
#입력 : n
#출력 : 1부터 n까지의 숫자를 더한 값

def sum_n2(n):
    sum = 0
    for x in range(1, n + 1):
        sum = sum + x
    return sum


print(sum_n2(n))

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

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

보통 입력 크기가 큰 문제를 풀 때는 O(1)인 알고리즘이 훨씬 더 빠르다.

연습문제

1-1) 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for 반복문으로 만들어라.

def sum_n(n):
    sum = 0
    for x in range(1, n + 1):
        sum = sum + x * x
    return sum

print(sum_n(10))

1-2) 연습 문제 1-1 프로그램의 계산 복잡도는 O(1)과 O(n) 중 무엇인가?
> O(n)

1-3) 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 공식은 n(n+1)(2n+1)/6로 알려져 있다. for 반복문 대신 이 공식을 이용하면 알고리즘의 게산 복잡도는 O(1)과 O(n) 중 무엇이 되는가?
> O(1)

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10