문제
N x N개의 수가 N x N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 2 | 3 | 4 | 5 |
| 3 | 4 | 5 | 6 |
| 4 | 5 | 6 | 7 |
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
제한사항
시간 제한: 1초
메모리 제한: 256MB
입출력 예
예제 입력 1
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4예제 출력 1
27
6
64예제 입력 2
2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2예제 출력 2
1
2
3
4문제 유형 분류
- 누적합 (2차원 Prefix Sum)
- 구간 합 처리
- 구현
시간 복잡도 + 공간복잡도 추정
- 표 생성: O(N)
- 2차원 누적합 배열 생성: O(N)
- 각 쿼리 처리: O(1) (누적합 이용 시)
- 총 쿼리 수: 최대 100,000 → 브루트포스로 하면 시간 초과 발생
총 시간 복잡도 : O(N + M)
공간 복잡도: O(N)
적합한 알고리즘 / 자료구조
- 2차원 누적합(Prefix Sum)
- 일반 리스트 arr와 누적합 배열 prefix_sum 2개 사용
필요한 라이브러리
import sys
input = sys.stdin.readline시간 초과 방지를 위해 빠른 입력 함수 사용
최악의 경우 시뮬레이션
- N = 1024, M = 100000일 때
- 단순하게 브루트포스로 각 영역의 합을 직접 더하면 O(N * M) → 최악 1000억 연산 → 시간 초과
- 2차원 누적합으로 변환 시 → O(M) 쿼리 처리 가능
접근 방법
- 입력을 받고 arr이라는 2차원 배열을 만든다.
- 2차원 누적합 배열 prefix_sum을 만든다.
- prefix_sum[i][j] = arr[1][1]부터 arr[i][j]까지의 합
- prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1] + arr[i][j]
- 쿼리 (x1, y1, x2, y2)에 대해 합을 구하는 공식 사용
S = prefix[x2][y2]
- prefix[x1-1][y2]
- prefix[x2][y1-1]
+ prefix[x1-1][y1-1]- 쿼리마다 위 공식을 써서 답을 출력한다.
최종 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = [[0] * (n+1)] # 1-based index를 위해 padding
for _ in range(n):
arr.append([0] + list(map(int, input().split())))
# 누적합 배열 생성
prefix = [ [0] * (n + 1) for _ in range(n + 1) ]
for i in range(1, n + 1):
for j in range(1, n + 1):
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j]
# 쿼리 처리
for _ in range(m):
x1, y1, x2, y2 = map(int, input().split())
res = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
print(res)import sys
input = sys.stdin.readline
n, m = map(int, input().splut())
arr = [[0] * (n+1)]
'''
첫 번째 줄이 4 3일 경우
arr = [[0] * (n+1)] 해석
n = 4이니까 n + 1 = 5
즉, arr = [[0, 0, 0, 0, 0]]
"0번째 행을 dummy로 채워넣기"
'''
for _ in range(n):
arr.append([0] + list(map(int, input().split())))
'''
다음 입력이 주어진다면
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
arr =
[[0, 0, 0, 0, 0],
[0, 1, 2, 3, 4],
[0, 2, 3, 4, 5],
[0, 3, 4, 5, 6],
[0, 4, 5, 6, 7]]
'''
for i in range(1, n + 1):
for j in range(1, n + 1):
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j]
'''
arr =
j→ 1 2 3 4
i↓ -----------------
1 | 1 2 3 4
2 | 2 3 4 5
3 | 3 4 5 6
4 | 4 5 6 7
prefix[2][3]을 계산한다고 해보자.
우리가 원하는 영역
(1, 1) (1, 2) (1, 3)
(2, 1) (2, 2) (2, 3)
6칸의 합을 구하고 싶음
prefix[2][3] =
prefix[1][3] <- 위쪽 누적합
+ prefix[2][2] <- 왼쪽 누적합
- prefix[1][2] <- 겹치는 영역 제거
+ arr[2][3] <- 현재 셀 값 더함
prefix[1][3]: (1, 1) ~ (1, 3) -> 1 + 2 + 3 = 6
prefix[2][2]: (1, 1) ~ (2, 2) -> 1 + 2 + 2 + 3 = 8
prefix[1][2]: (1, 1) ~ (1, 2) -> 1 + 2 = 3
arr[2][3]: -> 4
prefix[2][3] = 6 + 8 - 3 + 4 = 15
'''추가 팁 / 주의사항 / 많이 실수하는 점
| 1-based index 사용 | 누적합 공식을 간단하게 만들기 위함. arr[0][*], arr[*][0]은 0으로 padding |
|---|---|
| 빠른 입력 | 입력 수가 많기 때문에 input() 대신 sys.stdin.readline() 사용 |
| 음수 값 없음 | 배열 값이 0 이상이므로 누적합 계산에서 음수로 인한 오류 걱정 X |
| (x1, y1) > (x2, y2) 없음 | 문제에서 항상 x1 ≤ x2, y1 ≤ y2 보장 |
왜 0-based가 아닌 1-based로 arr과 prefix_sum 배열을 만드는가?
2차원 누적합(Prefix Sum) 공식을 단순화하기 위해 사용
0-based index를 쓴다면 (0, 0)좌표도 실제 데이터로 사용해야 하지만 prefix[x1-1][y2] 또는 prefix[x1-1][y1-1]에서 -1이 나오면 인덱스 에러가 남 → if x1 == 0일 때는 별도 처리, 예외처리 코드를 매번 넣어줘야 함
누적합 공식은 어떻게 유도되었는가?
-
한 번에 직접 더한다면?
total = 0 for i in range(x1, x2+1): for j in range(y1, y2+1): total += arr[i][j]시간복잡도: O((x2 - x1 + 1) * (y2 - y1 + 1))
최악의 경우 1024 x 1024 = 1,048,576번 덧셈
쿼리 100,000개면 1000억번 연산 = 터짐
-
미리 계산해두는 방식 필요
한 번만 전체를 훑고, 쿼리마다 바로 결과를 꺼내자
이걸 가능하게 하려면 직사각형을 부분 합들로 나누는 방식이 수학적으로 가장 효율적
prefix[i][j] = (1,1) ~ (i,j)의 합이걸 만들 때 전체를 매번 더하면 O(N²),
하지만 부분을 누적하면서 만들면 O(1)씩 누적 가능
-
왜 “가로 + 세로 - 겹침 + 자기” 구조인가?
j i ┌─────────────┐ │ │ │ │ ← prefix[i][j] (전체) │ │ └─────────────┘- prefix[i-1][j]: 위쪽 전체
- prefix[i][j-1]: 왼쪽 전체
- prefix[i-1][j-1]: 위+왼쪽 겹침 (빼줘야 함)
- arr[i][j]: 현재 셀
방식 시간 복잡도 설명 직접 더하기 O(N²) 쿼리마다 전체 계산 누적합 사용 O(1) 덧셈 4번이면 끝 덧셈 연산의 중복을 없애고 사전 계산한 값으로 한 번에 즉시 꺼내기 위해
- 이 계산을 하면 최대 100,000개 쿼리도 즉시 처리 가능
- 공식이 덧셈/뺄셈만으로 계산 가능해서 CPU에 부담 없음
- 겹치는 영역만 잘 제거해주면 여러 방향으로 응용 가능 (3차원도 가능)
