백준 11660 파이썬, 구간 합 알고리즘, 2차원 배열

백준 11660 : 구간 합 구하기 5

문제

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

백준 11660번

답안 코드 :

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = [[0] * (n + 1)]
D = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        # 구간 합 구하기
        D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    # 구간 합 배열로 질의에 답변
    result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1]
    print(result)

 

 

생각 :

구간 합
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
* 코딩 테스트에서 사용 빈도가 높다!!!

구간 합의 핵심 이론
-구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
-합 배열은 기존의 리스트 데이터를 전처리한 배열이라고 생각하자. 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
- 합 배열 만드는 공식
S[i] = S[i - 1] + A[i]
- 위의 합 배열을 이용하여 구간 합 역시 쉽게 구하기 가능
S[j] - S[i - 1] #i에서 j까지 구간 합


# 질의의 개수가 100,000 이므로 질의마다 합을 구하면 안 되고, 구간 합 배열을 이용하자
# 구간 합 배열이 1차원에서 2차원으로 확장된 것

# 구간 합 구하기
# D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]

# 구간 합 배열로 질의에 답변
# result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1]