[Career] 누적합 알고리즘

tag: #알고리즘

[!faq] 누적합 이란?

• 말 그래도 구간의 누적합은 구하는 문제.
• 시간복잡도는 최악의 경우 O(n^2)의 시간복잡도를 가지며 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식이다.
• 하지만 Prefix sum 방식을 사용하면 O(N)으로 해결 가능!!!🎉

ex) 크기가 5인 arr 배열에서 3번 Index 와 5번 Index 구간의 구간합을 구한다고 가정한다면, 누적합은 arr[0b까지의 누적합] - arr[0a-1 까지의 누적합] 으로 표현될 수 있다.

b-a 구간의 누적합을 구하기 위해선 b구간까지의 합 - a-1 구간까지의 합을 빼주면 된다.

1. 배열선언

int[] arr = {7, 6, 3, 2, 1}; //배열
// 누적합 : {7 13 16 18 19}
for(int i=0; i<=5; i++) {
	arr[i] = arr[i-1] + arr[i];
}
// [3,5] 구간 누적합 구하기
System.out.println(arr[5] - arr[3-1]);

2. 각 인덱스값에 누적합 저장
3. 3번 구간과 5번 구간 사이의 누적합을 구하려면 겹치는 1,2 구간을 제외해줘야 됨. 즉, 2번의 인덱스의 누적합을 빼줘야함. ![[Pasted image 20231026220121.png]] 분홍색 부분이 겹치는 부분, 즉 빼줘야 하는 부분이고 검은색 부분이 답을 구할 범위이다.

SWEA 파리 퇴치

요구조건

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이려고 한다. 죽은 파리의 개수를 구하라

제약사항

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 갯수는 30 이하 이다.

입력

첫 줄에는 테스트 케이스 T가 주어지고, 그 아래로 각 테스트 케이스가 주어 진다. 각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고, 다음 줄에 N 줄에 걸쳐 N x N 배열이 주어진다.

누적합 알고리즘을 이용하여 푸는거라고 댓글을 봤는데 일단 어느정도? 이해한 상태.

	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	for(int t = 1; t<= T; t++) {
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] map = new int[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		int start = 0; 첫 파리채 값
		for(int i=0; i<M; i++) {
			for(int j=0; j<M; j++) {
				start += map[i][j];
			}
		} // (0,0) ~ (M,M)의 파리채로 잡을 수 있는 파리 수 초기화
		int maxSum = start; // 파리채가 내려쳐서 죽일 수 있는 가장 큰 값, ans
		for(int i = 0; i< N-M+1; i++) {
			int sum = start; // 오른쪽으로 한칸씩 이동할 때 사용할 sum
			for(int j=0; j<N-M; j++) {
				for(int k=0; k<M; k++) {
					sum += map[i + k][j + M]; // 오른쪽으로 한칸 이동해서 파리채 영역으로 들어온 값 더해주고
					sum -= map[i +k][j] // 이동해서 파리채 영역 밖으로 나가게 된 값 뺴주고
				}
				maxSum = Math.max(maxSum, sum);
			}
			if (i < N - M) { // 마지막 i일때는 다음 칸 없으므로 그 전까지만
				for (int k = 0; k < M; k++) {
					start += map[i + M][k]; // 아래로 한칸 이동해서 파리채 영역으로 들어온 값 더해주고
					start -= map[i][k]; // 이동해서 파리채 영역 밖으로 나가게 된 값 뺴주고
				}
			}
			maxSum = Math.max(maxSum, start);
		} // 파리채 이동 for
	}
	System.out.printf("#%d %d\n", t, maxSum)



	}

SWEA에서 입출력 기준이 Scanner 이므로 Scanner 사용

문제 접근 방법

1. 완전탐색 알고리즘
2. 누적합 알고리즘??
3. 4중 for문 나중에 추후에 다시 풀어볼 문제