알고리즘108 :: 구간합 (JAVA)

구간의 합을 빠르게 구하고자 할때 Priefix sum을 미리 구해서 답을 도출해냅니다.

누적합이 특정배열에 담기는것으로 상수시간안에 답을 도출해낼 수 있습니다. 

10, 20, 30, 40, 50 인 경우 

10, 30, 60, 100, 150 으로 누적합 테이블을 생성할 수 있습니다. 

이때 left가 1이고 rightrk 3인 구간의 합을 구하는 문제가 주어질 경우 간딴하게 Array[3] - Array[1-1] 의 값으로 답을 결정할 수 있습니다. (식 Array[right] - Array[Left-1]) 

package test;
 
import java.util.*;
public class 구간합알고리즘 {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		int[] data = {10, 20, 30, 40, 50};
		ArrayList<Integer> al = new ArrayList<>();
		
		int sum = 0;
		al.add(sum);
		for(int i=0; i<data.length; i++) {
			al.add(sum+=data[i]);
		}
		int left = 2;
		int right = 3;
		System.out.println(al.get(right)-al.get(left-1));
	}
 
}

*ref : 동빈나 유튜브