[알고리즘]1부터 n까지의 합 구하기
2 min readMar 28, 2020
- 입력: n
- 문제: 1부터 n까지의 합을 구하는 절차
- 출력: 1부터 n까지의 합
- 방법1
- 변수 s = 0 을 만들어 해당 변수에 i 라는 변수를 만들어 1씩 추가하며 만들어지는 누산값이 결과값이 된다.
- 두개의 변수 필요. 누산값을 담을 변수 s 와 1씩 반복하여 더할 변수 i
- 해당 변수를 더하는 과정을 입력값 n 에 따라 반복하여 실행하여 누산값을 결과값으로 한다.
- python
def sum_n(n): s = 0 for i in range(1, n+1): s = s + i return s data = 5 result = sum_n(data) print(result)- rust
fn main() { let result = sum_n(5); println!("{}", result) } fn sum_n(n: u32) -> u32 { let mut s = 0; for i in 1..n+1 { s = s + i; } return s; }- 방법2
- 가우스가 풀었다는 방식
- 1부터 100까지의 합을 구한다고 했을 때, 1+100 = 101, 2+99 = 101 이며, 이러한 방식으로 101 이 50 번 나온다.
- 위를 식으로 풀어보면 n * (n+1) / 2 가 된다. ((n+1) * n / 2 가 논리적으로 이해하기는 더 쉬운듯 하다.)
- python
def sum_n(n): return n * (n+1) // 2 data = 5 result = sum_n(data) print(result)- rust
fn main() { let result = sum_n_2(5); println!("{}", result) } fn sum_n_2(n: u32) -> u32 { return n * (n+1) / 2 }- 계산 복잡도
- 방법1: 덧셈 n 번 → O(n)
- 방법2: 덧셈, 곱셈, 나눗셈 각 한번 (총 세번) → O(1)
