[알고리즘] 누적합(Prefix Sum) +Java객체 배열 선언 & 생성

 

 

 
 
 

누적합 (Prefix Sum)

---

 
누적합이란? 

• 배열의 인덱스가 증가함에 따라 그 누적된 합을 미리 구해 놓는 것, '전처리' 라고도 함.
• arr배열을 일일히 for문으로 돌면서 합을 구하면 되는것 아닌가란 의문을 던질 수 있다. 하지만 이렇게 하면 시간복잡도 측면에서 성능이 저하된다. (테스트케이스에서 시간초과 문제가 발생하기도 함..) 그러므로 누적합을 미리 구하여 사용한다.

 
 
 
누적합 구현

• 크기가 10인 arr 배열의 누적합을 구해보자

 
 

---

 

1.  누적합으로 [a] ~ [b] 의 합을 구하기.

 

    "  acc [ b ] - acc [ a - 1 ]  "

 
 
 

2. acc배열을 채우기

인덱스 0 일때는 arr[0] 그 자체가 된다.
그 이후부터는 acc[i] = acc[i-1] + arr[i]
 
 

" acc[0]=arr[0] "
 
" acc[i] = acc[i-1] + arr[i] "
 

for(int i=0;i<n;i++) {
	if(i==0) {
    acc[i]=arr[i];
	}
    else {
	acc[i]=acc[i-1]+arr[i];
	}
}

 
 
 
 

---

 
 
예제
 
Q. 배열의 크기 n인 배열에 n개의 원소 개수를 입력 받고,
물음의 횟수 m을 입력 받고, 순서쌍 (a,b)는 m개 들어올때,
a~b의 합을 구하시오.
 
 
 
 
A. 
순서쌍 인덱스를 포함하여 배열안에서 합을 구하면 된다.
이때 누적합을 사용하면 이렇게 풀 수 있다.

package com.com.practice;

import java.util.Scanner;

class Info{
	int a;
	int b;
	
}

public class Main {
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
	
		int n= sc.nextInt();
		int arr[]=new int[n];
		int acc[]=new int[n];
		
		//arr,acc 입력받기
		for(int i=0;i<n;i++) {
			arr[i]=sc.nextInt();
			if(i==0) {
				acc[i]=arr[i];
			}
			else {
				acc[i]=acc[i-1]+arr[i];
			}
			
			
		}
		int m = sc.nextInt();
		
		//순서쌍 a,b 입력받기
		Info[] info = new Info[m];
		for(int i=0;i<m;i++) {
			info[i]=new Info();
			info[i].a=sc.nextInt();
			info[i].b=sc.nextInt();
		}
		
		for(int i=0;i<m;i++) {
			
			if((info[i].a)==0) {
				System.out.println(i+1+"번째 합: "+ acc[info[i].b]);
			}
			else System.out.println(i+1+"번째 합: "+ (acc[info[i].b]-acc[info[i].a-1]));
			
			
		}
		
		
		
		return;
	}
	
	

}

 
 
 
 
 
+

객체 배열의 선언 및 생성 방법

 
Book 객체 3개를 배열 형태로 만들어 사용하기 위해서 먼저 아래와 같이 코드를 작성하게 되면,
레퍼런스 변수 b와 Book 객체에 대한 레퍼런스 변수 3개가 생성됩니다. 
 
   Book[ ] b = new Book[3];
 
이렇게 선언하게 되면 Book 객체를 담을 레퍼런스 변수 3개가 배열형태로 생성됩니다. 
주의할 점은 아직 Book 객체가 만들어진것은 아니기 때문에, Book 객체를 사용하기 위해서는 아래와 같이 Book 객체를 생성해 주어야 합니다. 
 
   b[0] = new Book( );
   b[1] = new Book( );
   b[2] = new Book( );
 
 
 
 
 
 
 
 
 
 
출처: https://kadosholy.tistory.com/90 [KADOSHoly:티스토리]