알고리즘 코드카타. 두 정수의 합(2024-06-18)

문제 개요

문제 요약 : 두 정수 a b가 주어지고 a ~ b 사이의 모든 정수의 합을 구하라

 

이 문제는 for문으로 a부터 b까지 하나씩 더하면 문제는 해결된다.

첫번째 풀이

그러나 이는 단순한 방법이며 숫자가 커질수록 시간복잡도가 커진다. O(n)인 연산을 O(1)로 낮추는 방법이 있다. 등차수열의 합 공식을 사용하면 된다. 

 

---

등차수열을 이용한 풀이)

등차수열 합 공식

여기서 n은 항의 개수, a는 첫 번째 항, l은 마지막 항이다.

 

등차수열의 합의 공식을 설명하기엔 너무 길어지므로 따로 공부해보는것이 좋을것이다.

 

이렇게 코드를 개선하면 시간복잡도를 획기적으로 개선할 수 있다.