반응형 O(1) (1) 썸네일형 리스트형 1부터 100까지 더하기 알고리즘 문제를 O(1) 시간으로 푸는 법 (가우스 법칙 원리) 코딩 테스트에서 가끔 1부터 숫자 n까지 더하라는 문제가 나온다. 총합 = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n 예시: 숫자 n이 5일 경우 총합 = 1 + 2 + 3 + 4 + 5 위와 같이 반복문으로 풀면 되지만 문제점은 숫자 n이 커질수록 반복문 실행 숫자가 숫자 n만큼 동일하게 커진다. 즉, 이 알고리즘의 시간 복잡도는 O(n)이 된다. 하지만 가우스 법칙으로 이 문제를 O(1)으로 풀 수 있다. 가우스 법칙 공식은 아래와 같다. 총합 = (n+1)n / 2 아니 시8 이게 가능한가?라고 궁금증이 생기고 왜 저 공식이 가능한지 알아보자. 처음 보여준 공식을 두 개를 더해보자 (이때 두 번째 공식의 숫자 나열을 뒤집어보자, 어차피 뒤집어도 계산에 지장이 없지만 가우.. 이전 1 다음