0부터 N까지의 합 구하기 (in javascript)

최근에 코딩 공부를 위해 수강한

 

Code | States (부트 캠프)의

 

 

Pre 코스를 통해 Javascript와 Front-End에 대해 학습할 수 있었습니다.

 

처음에는 level 1의 JavaScript Basic 과제를 통해 기초를 배워나갈 수 있었는데요.

 

[3. 반복문] 01_sum에 있는 문제를 아래와 같이 for문을 활용하여 Sum함수를 아래와 같이 작성하였습니다.

 

 

0부터 N까지 순차적으로 더한 Sum 함수

function sum(n) {

  let result = 0;

  for (let i = 0; i <= n; i++) {

    result = result + i;

  }

  return result;

}

 

위와 같이 문제를 풀 수 있지만, level 4-2 에서 배운 알고리즘과 복잡도에 의하면 O(n)의 Big-O Notation으로 표기할 수 있습니다.

 

즉, 위의 함수는 for문을 통해 N번 실행하게 되며, N이 커질 수록 실행 시간이 비례하여 증가하게 됩니다.

 

하지만 우리는 예전에 수학 시간에 배웠던 등차수열을 활용하여 이 문제를 풀 수 있습니다.

 

 

(첫 항이 1이며, 공차가 1일 때 공식)

 

 

-> 증명은 단순하게 그림으로

수학적 공식을 활용한 Sum(0~N) 함수

function sum(n) {

	return n * (n+1) / 2;

}

 

이를 활용하면 입력 n이 몇이 들어오던 간에, 더하기(+), 곱하기(*), 나누기(/) 총 세 번으로 리턴 값을 돌려주게 됩니다.

 

이는 처음에 for문을 활용한 Sum함수에서 n <= 3일 때를 제외하고는, O(1)로 계산 시간에서 이득을 볼 수 있습니다. 

 

결론 : 같은 결과를 내는 함수도 알고리즘을 활용하여 작성하면 더 효율적으로 자원(메모리, 시간 등)을 활용할 수 있다.

 

등차수열에 대한 증명은 아래 링크 참조

https://mathbang.net/609