누적합 알고리즘

코딩테스트에서 자주 나오는 누적합(Prefix Sum) 알고리즘을 정리합니다. 구간 합을 효율적으로 구하는 방법을 배웠습니다.

📚 누적합이란?

누적합은 구간의 합을 구하는 문제에서 사용하는 알고리즘입니다.

일반적인 방법:

• 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식
• 시간복잡도: 최악의 경우 O(n²)

Prefix Sum 방식:

• 미리 누적합 배열을 만들어두고 구간 합을 빠르게 계산
• 시간복잡도: O(N)으로 해결 가능

기본 원리

크기가 5인 arr 배열에서 3번 Index와 5번 Index 구간의 구간합을 구한다고 가정하면, 누적합은 다음과 같이 표현할 수 있습니다:

• arr[0~b까지의 누적합] - arr[0~a-1까지의 누적합]

즉, b-a 구간의 누적합을 구하기 위해서는 b구간까지의 합에서 a-1 구간까지의 합을 빼주면 됩니다.

누적합 배열 생성 방법

1. 배열 선언 및 누적합 계산

java복사
int[] arr = {7, 6, 3, 2, 1}; // 원본 배열
int[] prefixSum = new int[arr.length + 1]; // 누적합 배열 (인덱스 0은 0으로 유지)

// 누적합 배열 생성 (인덱스 1부터 시작)
prefixSum[0] = 0;
for(int i = 1; i <= arr.length; i++) {
    prefixSum[i] = prefixSum[i-1] + arr[i-1];
}
// prefixSum: {0, 7, 13, 16, 18, 19}

// [3, 5] 구간의 누적합 구하기 (인덱스는 0부터 시작하므로 실제로는 [2, 4] 구간)
// 구간합 = prefixSum[5] - prefixSum[2] = 19 - 7 = 12
// 실제 값: arr[2] + arr[3] + arr[4] = 3 + 2 + 1 = 6
// 주의: 인덱스가 1-based인지 0-based인지에 따라 계산이 달라짐

2. 각 인덱스값에 누적합 저장

누적합 배열의 각 인덱스 i에는 원본 배열의 0번부터 i-1번까지의 합이 저장됩니다.

3. 구간합 계산 원리

구간 [a, b]의 합을 구하려면:

• prefixSum[b+1] - prefixSum[a] (0-based 인덱스 기준)
• prefixSum[b] - prefixSum[a-1] (1-based 인덱스 기준)

예시: 3번 구간과 5번 구간 사이의 누적합을 구하려면 (1-based 기준)

• prefixSum[5] - prefixSum[2]
• 이는 arr[04]의 합에서 arr[01]의 합을 뺀 것
• 즉, arr[2~4]의 합이 됨

시각적 설명:

원본 배열: [7, 6, 3, 2, 1]
인덱스:    0  1  2  3  4

누적합:    [0, 7, 13, 16, 18, 19]
인덱스:     0  1   2   3   4   5

구간 [2, 4]의 합:
prefixSum[5] - prefixSum[2] = 19 - 7 = 12
실제 값: 3 + 2 + 1 = 6 (인덱스 2, 3, 4)

분홍색 부분이 겹치는 부분(제외해야 할 부분), 검은색 부분이 답을 구할 범위

SWEA 파리 퇴치

요구조건

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

제약사항

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

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

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

입력

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

이 문제는 누적합 알고리즘을 활용하여 해결할 수 있습니다. 위 코드는 슬라이딩 윈도우 기법을 사용하여 파리채를 이동시키면서 효율적으로 계산하는 방식입니다.

알고리즘 설명

1. 초기 파리채 영역 계산: (0,0)부터 (M-1, M-1)까지의 파리 수를 계산
2. 오른쪽으로 이동: 파리채를 오른쪽으로 한 칸씩 이동하면서 새로 들어온 열을 더하고 나간 열을 뺌
3. 아래로 이동: 한 행이 끝나면 아래로 이동하면서 새로 들어온 행을 더하고 나간 행을 뺌
4. 최대값 갱신: 각 위치에서의 파리 수를 계산하여 최대값을 갱신

이 방식의 시간 복잡도는 O(N²)로, 완전 탐색의 O(N² × M²)보다 훨씬 효율적입니다.

java복사
	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. 누적합 알고리즘: Prefix Sum을 활용한 효율적인 방법
3. 4중 for문: 간단하지만 비효율적인 방법

제가 처음에는 4중 for문으로 접근했지만, 누적합 알고리즘을 배운 후에는 더 효율적으로 해결할 수 있게 되었습니다. 나중에 다시 풀어볼 문제로 남겨두었습니다.