[Python] 누적합 - 백준 2167. 2차원 배열의 합

📝 문제 요약

🔗  https://www.acmicpc.net/problem/2167

 < 입력 >
N M
N행 M열의 배열 (N줄로 주어짐)
반복 횟수
반복 횟수 만큼의 i, j, x, y

 < 출력 >
반복 횟수 만큼의 구간합

📜 처음 낸 코드 - 시간 초과

N, M = map(int, input().split())
matrix = []
for _ in range(N):
	temp = list(map(int, input().split()))
	matrix.append(temp)

rep = int(input())
for _ in range(rep):
	i, j, x, y = map(int, input().split())
#	print(sum(matrix[i-1:x][j-1:y]))
	answer = 0
	for k in range(i-1, x):
		tmp = sum(matrix[k][j-1:y])
		answer += tmp
	print(answer)

리스트 슬라이싱, sum()으로 냅다 더하기.

 

🔧 문제점

시간 복잡도를 계산해보자.

N, M = map(int, input().split())	# O(1)
matrix = []					
for _ in range(N):
	temp = list(map(int, input().split()))
	matrix.append(temp)				# matrix 초기화 : O(NM)

rep = int(input())					# O(1)
for _ in range(rep):				
	i, j, x, y = map(int, input().split())
#	print(sum(matrix[i-1:x][j-1:y]))
	answer = 0
	for k in range(i-1, x):			# 최대 O(N)
		tmp = sum(matrix[k][j-1:y])  # 최대 O(M) (리스트 슬라이싱 합 계산)
		answer += tmp				# 해당 반복문 O(NM)
	print(answer)

👉 O(rep*NM)

 

입력값의 범위를 봤을 때, 

(1 ≤ N, M ≤ 300)이고 K(1 ≤ K ≤ 10,000)이다. (내 코드에선 K를 rep라고 했다)

 

내가 쓴 코드와 같은 방식을Brute Force라고 한다.

이 방법을 쓰면 가능한 모든 경우를 단순무식하게 하나씩 다 확인한다. 완전 탐색도 이렇게 부른다. 

Brute Force는 입력 크기가 작을 때에 ( N <= 1000이면 O(N^2)도 가능 ) 사용하면 구현이 간단해서 좋을 수 있다.

  cf. 위 괄호 속의 기준은 CPU의 연산 속도를 기준으로 한 경험적인 값이다.

       1초를 기준으로 약10^8(1억)개의 연산이 가능하다고 가정.

 

Brute Force를 최적화하기 위해서

우리가 아는 다양한 알고리즘(누적합, 슬라이딩 윈도우, 분할 정복, 동적 계획법(DP), 정렬, 해시맵 등)을 사용할 수 있다.

✅ 통과 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
p_sum = [ [0]*(M+1) for _ in range(N+1) ]
for k in range(1, N+1):
	for l in range(1, M+1):
		p_sum[k][l] = (
        	matrix[k-1][l-1] + 
            p_sum[k-1][l] + 
            p_sum[k][l-1] - 
            p_sum[k-1][l-1]
        )

rep = int(input())
for _ in range(rep):
	i, j, x, y = map(int, input().split())
	result = p_sum[x][y] - p_sum[i-1][y] - p_sum[x][j-1] + p_sum[i-1][j-1]
	print(result)

👉 O(NM) + O(rep)

 

코드를 찬찬히 읽으며 matrix와 p_sum의 그림을 그려 생각해보면 알 수 있다.

이해하니 명쾌하고 깔끔해서 참 좋았다.✨

 

➕ matrix는 List comprehension으로 입력 받기

 

➡️ to be continued...

추천 문제 : 백준 11660번 구간 합 구하기 5, 프로그래머스 연속 부분 수열 합 구하기

슬라이딩 윈도우 알고리즘