💻 CS [Computer Science]/🪵 DataStructure [자료구조] 썸네일형 리스트형 [자료구조 스터디] 합 배열 / 구간 합 구하기 ▶ 구간 합 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘 ▶ 구간 합의 핵심이론 구간 합 알고리즘을 이용하려면 먼저 합 배열을 구해야 함. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의함. ▶ 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] 이렇게 구현된 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있음. 누적합 배열은 항상 일반 배열 보다 인덱스 +1 임. 사람이 질의를 할 때 0번 인덱스를 고려하지 않고 하기 때문에 1번 인덱스로 시작을 함. ▶ 합 배열 정의 : 자바 1초 -> 1억번의 연산 S[i] = A[0] + A[1] + A[2] + …. + A[A-i] + A[i] // 0부터 A[i] 까지의 합 합 배열은 기존의 배열을 전처리한 .. 더보기 이전 1 다음
