2차원 배열 누적합(합배열) 개념 이해하기

(chatGPT를 통해 정리한 내용입니다.)

 

1. 2차원 배열 누적합(합배열) 개념

1.1. 개념 소개

• 누적합(prefix sum)
  : 1차원 배열에서 특정 구간의 합을 빠르게 구하기 위해 미리 구간의 합을 저장해두는 기법을 말합니다.
• 2차원 배열 누적합
  : 2차원 배열에서 어떤 직사각형 영역(부분행렬)의 합을 빠르게 구하기 위해 미리 **누적합 배열(dp)**을 만들어 두는 방법입니다.

1.2. 왜 사용하는가?

• 문제 상황:
  "N×M 크기의 배열이 주어지고, Q개의 질의(query)가 주어집니다. 각 질의는 (x1, y1)부터 (x2, y2)까지의 부분행렬에 포함된 원소들의 합을 구하는 문제"
• 직접 합산:
  매 질의마다 해당 영역을 순회하면 시간 복잡도가 O(N×M)이고, Q가 많을 경우 시간 초과가 발생할 수 있습니다.
• 누적합 사용:
  한 번 미리 누적합 배열을 만들어두면, 각 질의를 O(1) 시간에 처리할 수 있습니다.

1.3. 2차원 누적합 배열(dp) 만드는 방법

원본 배열을 arr[ ][ ]라고 하고, 누적합 배열을 dp[ ][ ]라고 하겠습니다.
**dp[i][j]**는 원본 배열에서 **(1,1)**부터 **(i,j)**까지의 모든 원소 합을 의미합니다.

 

계산 공식은 다음과 같습니다.

dp[i][j] = arr[i][j] + dp[i−1][j] + dp[i][j−1] − dp[i−1][j−1]

 

• 이유:
  • dp[i-1][j]는 위쪽 영역의 합
  • dp[i][j-1]은 왼쪽 영역의 합
  • 위 두 영역을 합하면 **(1,1)부터 (i-1,j-1)**에 해당하는 영역이 두 번 포함되므로, 이를 빼줍니다.

[주의]
인덱스 범위를 벗어나지 않도록, 보통 dp 배열을 (N+1)×(M+1) 크기로 만들어 0행과 0열을 0으로 초기화하는 방식을 사용합니다.

1.4. 누적합 배열을 이용한 질의(부분합) 구하는 공식

구하고자 하는 영역이 **(x1, y1)**에서 **(x2, y2)**라면, 해당 영역의 합은 다음과 같이 구합니다.

부분합 = dp[x2][y2] − dp[x1−1][y2] − dp[x2][y1−1] + dp[x1−1][y1−1]

• 해석:
  • dp[x2][y2] : (1,1)부터 (x2,y2)까지의 전체 합
  • dp[x1-1][y2] : (1,1)부터 (x1-1, y2)까지의 합 → 위쪽 영역 제거
  • dp[x2][y1-1] : (1,1)부터 (x2, y1-1)까지의 합 → 왼쪽 영역 제거
  • dp[x1-1][y1-1] : 위쪽과 왼쪽 영역이 중복 제거된 부분을 다시 더해줌

---

2. 코딩테스트에서 자주 나오는 유형 예제

예제 문제: "2차원 배열의 부분합 구하기"

문제 설명:

• 입력:
  • 첫 번째 줄에 행의 개수 N과 열의 개수 M이 주어집니다.
  • 다음 N개의 줄에 M개의 정수가 주어집니다 (배열의 원소).
  • 그 다음 줄에 질의의 개수 Q가 주어집니다.
  • 이후 Q개의 줄에 x1, y1, x2, y2가 주어지며, 각 질의마다 (x1, y1)부터 (x2, y2)까지의 부분행렬 합을 구해야 합니다.
• 출력:
  • 각 질의마다 부분행렬의 합을 한 줄에 하나씩 출력합니다.

2.1. 예제 입력

4 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
3
2 2 3 4
3 1 4 5
1 1 4 5

 

2.2. 예제 출력

21
40
60

해설:

• 첫 번째 질의 (2,2)부터 (3,4)까지의 영역
  • 해당 영역의 원소:
    [4, 3, 2] (2번째 행, 24열)
    [3, 4, 5] (3번째 행, 24열)
  • 합: 4+3+2+3+4+5 = 21
• 두 번째 질의 (3,1)부터 (4,5)까지의 영역
  • 해당 영역의 합: 40
• 세 번째 질의 전체 영역 (1,1)부터 (4,5)까지의 합: 60

---

3. Java 코드 구현 및 자세한 풀이 해설

다음은 위 문제를 해결하기 위한 Java 코드 예제입니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // BufferedReader를 사용하면 입출력 속도가 빠름 (코딩테스트에서 자주 사용)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 1️⃣ 행(N)과 열(M) 입력받기
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        // 원본 배열 및 누적합 배열 (dp) 선언
        int[][] arr = new int[N+1][M+1];  // 1-indexed 사용 (편의를 위해)
        int[][] dp = new int[N+1][M+1];
        
        // 2️⃣ 원본 배열 입력 받기
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 3️⃣ 2차원 누적합 배열(dp) 계산
        // dp[i][j] = arr[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = arr[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            }
        }
        
        // 4️⃣ 질의(query) 개수 입력받기
        int Q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        // 5️⃣ 각 질의마다 (x1, y1)부터 (x2, y2)까지의 부분합 계산
        // 부분합 = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
        for (int q = 0; q < Q; q++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            int sum = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            sb.append(sum).append("\n");
        }
        
        // 6️⃣ 결과 출력
        System.out.println(sb.toString());
    }
}

---

4. 코드 해설

1. 입력 및 배열 초기화 (1-indexed 방식)

• 행과 열의 개수를 입력받고, 편의를 위해 인덱스를 1부터 사용합니다.
• arr[ ][ ]에 원본 데이터를 저장하고, dp[ ][ ]를 누적합 배열로 사용합니다.

2. 2차원 누적합 배열(dp) 계산

• 이중 for문을 사용하여 각 위치 (i, j)에 대해
  dp[i][j] = arr[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
  를 적용합니다.

3. 질의 처리

• 각 질의마다 (x1, y1)와 (x2, y2)를 입력받습니다.
• 누적합 배열을 이용해 O(1) 시간에 구간 합을 계산합니다:
• StringBuilder를 사용하여 결과를 저장한 후, 한 번에 출력합니다.

int sum = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];

 

 

4. 시간 복잡도

• 누적합 배열 계산: O(N×M)
• 각 질의 처리: O(1) per query
• 전체 시간 복잡도: O(N×M + Q) → N, M, Q가 커져도 빠르게 동작함

---

5. 정리 및 결론

• **2차원 배열 누적합(합배열)**은 여러 구간 합 질의를 빠르게 해결할 수 있도록 해주는 매우 유용한 기법입니다.
• 코딩테스트에서 자주 등장하는 문제 유형이며,
  한 번 dp 배열을 계산해두면 여러 질의를 O(1)에 처리할 수 있으므로 효율적입니다.
• 위 예제와 같이 문제를 풀면, 입력받은 2차원 배열의 부분합을 빠르게 계산하여 시간 초과 없이 문제를 해결할 수 있습니다.