2025.02.07 작성

📝 문제 요약

🔗 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)

🔧 문제점

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

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으로 입력 받기