구간 합
🤔 구간 합이란?합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.📌 합 배열을 이용한 구간 합 구하기예시)리스트 A = [15, 13, 10, 7, 3, 12]합 배열 S = [15, 28, 38, 45, 48, 60]합 배열을 구하는 공식 : S[i] = S[i] + A[i] 구간 합 구하기 : S[j] - S[i-1]리스트 A[2]부터 A[5] 까지 구간 합을 구하는 문제에서 합 배열을 통해 구하면,S[5] - S[1]로 계산할 수 있다. 시간 복잡도 O(1) 이 된다.합 배열을 사용하지 않고, 리스트로 구간 합을 구한다면,A[0] + ... + A[5] - (A[0]+A[1]) 로 구할 수 있고, 시간 복잡도는 리스트 길이만큼 탐색해야하기 때문에,시간 복잡도..
2023. 3. 16.