구간합__💡 구간합이란?__합배열을 이용해 시간복잡도를 줄이는 목적의 알고리즘__합배열 SS[i] = A[0] + a[1] + ... + A[i-1] + A[i] 기존의 배열을 전처리한 배열 기존 일정 범위의 합을 구하는 시간복잡도가 $O(N)$ 에서 $O(1)$ 로 감소합배열 만드는 법S[i] = S[i-1] + A[i];합배열에서 특정 구간 내의 합 구하는 법[부분합] j~i 사이 구간 구할때result = S[i] - S[j-1]; j 가 아닌 j-12~4 까지의 구간합을 구하고 싶으면 💡연관문제[G3] 10986 나머지 합[S1] 11660 구간합 5 [S3] 11659 구간합 4
CS & 알고리즘/알고리즘
소수란 1과 자기 자신 만을 약수로 가지는 수기본적인 소수 구하는 방법반복문을 통해 1과 자기 자신을 제외한 숫자로 나누었을때모두 % != 0 나머지가 0이 아니면 소수이다N 의 약수는 무조건 1 ~ $\sqrt{N}$ 안에 존재한다이 방법을 통해 시간복잡도 $O(\sqrt{n})$ 까지 감소 가능구현예시 double sqrt = Math.sqrt(N); for (int i = 2; i 위 코드에서 sqrt 를 for 문 안에 넣으면 반복문 돌때마다 계산하므로 비효율적for (int i = 2; i * i 으로 써도 동일함시간복잡도 : $O(\sqrt{n})$ 에라토스테네스의 체 활용방법특정 범위 내에서 여러 숫자가 소수인지 판별할때 유리한 알고리즘낮은 시간복잡도, 높은 공간복..
