11659

[알고리즘/Java] 구간 합(Prefix Sum)과 관련 예제(BOJ-11659)

[ 1 ] 정수 배열 A에서 특정 구간(i ~ j) 내 모든 원소의 합을 구하라 특정 배열이 주어지고 위와 같은 질문을 받는다면, 우리는 어떻게 특정 구간 내 모든 원소의 합을 구할 수 있을까? 시간 제한이 없고 배열 원소의 수가 적다면 단순히 선형 탐색으로 i ~ j 까지의 특정 구간 내 원소의 합을 구할 수 있을 것이다. 하지만, 배열 내 원소의 수가 매우 많고, 계산해야 할 특정 구간도 많이 주어진다면 위와 같은 선형 탐색은 오랜 시간이 소요될 것이다. [ 2 ] 구간 합(Prefix Sum) [2 - 1] 정의 구간 합 알고리즘을 활용하면 선형 탐색으로 O(n)이 소요되던 시간 복잡도를 O(1)으로 줄일 수 있다. 어떻게 이것이 가능한가? 우선 A라는 정수 배열이 있을 때 S라는 '합 배열'을 정..