문제 요약 : 두 정수 a b가 주어지고 a ~ b 사이의 모든 정수의 합을 구하라
이 문제는 for문으로 a부터 b까지 하나씩 더하면 문제는 해결된다.
그러나 이는 단순한 방법이며 숫자가 커질수록 시간복잡도가 커진다. O(n)인 연산을 O(1)로 낮추는 방법이 있다. 등차수열의 합 공식을 사용하면 된다.
등차수열을 이용한 풀이)
여기서 n은 항의 개수, a는 첫 번째 항, l은 마지막 항이다.
등차수열의 합의 공식을 설명하기엔 너무 길어지므로 따로 공부해보는것이 좋을것이다.
이렇게 코드를 개선하면 시간복잡도를 획기적으로 개선할 수 있다.
'TIL(사전캠프)' 카테고리의 다른 글
리버싱1. 13 ~ 20(2024-06-20) (0) | 2024.06.20 |
---|---|
유용한 함수들(Java) (2024-06-19) (0) | 2024.06.19 |
알고리즘 코드카타. 정수 제곱근 판별(2024-06-13) (0) | 2024.06.13 |
SQL 코드카타. 경기도에 위치한 식품창고 목록 출력하기(2024-06-12) (0) | 2024.06.12 |
알고리즘 코드카타. 자연수 뒤집어 배열로 만들기(2024-06-12) (0) | 2024.06.12 |