[모두의 알고리즘] 1부터 n까지의 합 구하기(python, Swift)

참고 교재: 모두의 알고리즘 with 파이썬

❓ 문제

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

입력: n
출력: 정수

🌀 기존 풀이

python

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

Swift5

public func sum_1ton(n: Int) -> Int {
    var sum:Int = 0
    for i in 1..<n+1 {
        sum += i
    }
    return sum
}

💭 분석

n=10일 경우 덧셈 연산을 10번, n=1000일 경우 덧셈 연산을 1000번 해야 한다. 따라서 기존 코드로 풀었을 경우, 시간복잡도는 O(n)

💡 시간복잡도 줄이기!

우리가 수학 시간에 1부터 10까지의 합을 계산하려고 하면,

 (10*11)/2

라고 계산한다. 따라서 이 공식을 일반화하면

(n*n+1)/2

이고, 이는 n의 크기와 상관없이 덧셈, 곱셉, 나눗셈을 한 번씩 수행하므로 시간복잡도는 O(1)이 된다.

❗️ 개선된 풀이

python

def sum_1ton(n):
    return (n * (n+1)) // 2 # 여기에서 // 이 기호는 정수 나눗셈!

Swift5

public func sum_1toN(n: Int) -> Int {
    return (n * (n + 1)) / 2
}

✔️ 연습문제

// 연습문제 1-1

public func sumPow_1toN(n: Int) -> Int {
    var sum = 0
    for i in 0...n {
        sum += Int(pow(Double(i), 2.0))
    }
    return sum
}

// 연습문제 1-2
// 답: O(n)

// 연습문제 1-3 : O(1)

public func sumPow_1toN(n: Int) -> Int {
    return (n * (n + 1) * ((2 * n) + 1)) / 6
}