[Python] 백준 11660번 구간 합 구하기 5 (ps. 0으로 이루어진 리스트 만들기([[] * n] vs [[] for i in range]))

문제 이해가 너무 안됐다. 글을 모호하게 써둔 것 같음..;;

(2,2) ~ (3,4)의 합을 구할 때 (3,1)이 빠지는 이유를 .. 흠

 

그래서 처음엔 구간 합을 총 누적으로 계산했었다.

n, m = map(int, input().split())
origin = list()
z = 0
result = list()

# 원본 배열 입력
for i in range(0, n):
    a = list(map(int, input().split()))
    origin.append(a)

# 합배열 생성
sum = [[0]*(n+1)]

for i in range(0, n):
    a = list()
    for j in range(0, n):
        z += origin[i][j]
        a.append(z)
    sum.append(a)

# 합배열 각 행 1열에 전 행 끝 숫자 추가
for i in range(1, n + 1):
    sum[i].insert(0, sum[i-1][n])

# x1, y1, x2, y2 입력
for i in range(0, m):
    x1, y1, x2, y2 = map(int, input().split())
    result.append(sum[x2][y2] - sum[x1][y1-1])

for i in range(0, m):
    print(result[i])

이렇게 하면 기존 배열이 왼쪽 사진일 때, 합배열을 오른쪽처럼 얻을 수 있다.

예시랑 답이 달라서 한참을 고민하다가 책의 문제 풀이를 봤는데 구간합 구하는 방식이 아예 달랐다.

나는 1차원적으로 생각한 거고 2차원적으로 접근해야 됐던 듯.. 그래서 (3, 1)이 빠지는 것 같다. 

 

1차원에서 구간 합이 S[ i - 1] + A [ i ] 였다면,

2차원에서 구간 합 구하는 공식은 D[ i ][ j ] = D[ i ] [ j - 1 ] +  D[ i - 1 ][ j ] - D[ i - 1 ][ j - 1 ] + A[ i ][ j ] 이다.

 

이게 뭔 ... ㅋㅋㅋ ㅠㅠ

그냥 외워야 하는 것 같다..

---

합 배열을 만들면서 또 다른 난관에 봉착했다

2차원 배열을 선언 했는데, 값 수정시 모든 행이 같이 변하는 것 ..

 

기존엔 다음과 같은 코드를 이용했다.

sum = [[0]*(n+1)]*(n+1)

예를 들어, sum[2][2] = 2 로 변경하면 모든 행의 [i][2]가 2로 변했다..

 

책의 풀이는 다음과 같다.

sum = [[0]*(n+1) for i in range(n+1)]

 

둘의 차이가 뭔지 도저히 모르겠어서 구글링을 했다.

https://m.blog.naver.com/wjddudwo209/221253421426

https://leedakyeong.tistory.com/entry/Python-2-dimension-list

뭔가 같은 값을 바라보도록 메모리가 저장되어 있는 듯 하다.

 

아무튼.. 2차원 이상의 배열을 초기화 할 때는 배열 내에 for 문을 이용해야 한다.

---

기존에 짠 코드는 x2,y2 에서 x1,y1-1의 값을 빼면 됐지만, 바뀐 코드에서는 나머지 값을 모두 빼줘야 한다.

아래 사진을 예로 들자면, 노란 값의 합을 구하는 것이기 때문에 빨간 부분에서 파란 부분을 모두 빼야 한다.

 

이를 위해서 빨간 부분의 합에서 파란 부분, 초록 부분을 뺀 후, 2번 빠진 노란 부분을 한 번 더해주면 된다.

공식으로 살펴보면 D[x2][y2] - D[x2][y1-1] - D[x1-1][y2] + D[x1-1][y1-1]이 된다.

 

# 구간 합 구하기 5
# N*N개의 수가 N*N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
# 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2가 주어진다.
# 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다.

n, m = map(int, input().split())
origin = list()
result = list()

# 원본 배열 입력
for i in range(0, n):
    a = list(map(int, input().split()))
    origin.append(a)

# 합배열 생성
sum = [[0]*(n+1) for i in range(n+1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + origin[i - 1][j - 1]

# x1, y1, x2, y2 입력
for i in range(0, m):
    x1, y1, x2, y2 = map(int, input().split())
    result.append(sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1])

for i in range(0, m):
    print(result[i])

---

새로운 문제를 만났다.. 시간초과.. ^__ㅠ..

 

시간 복잡도를 아무리 계산해도 답안과 차이가 없어서 고민을 많이 했다.

답안과 비교해보니 다른 점은 임포트 부분이었다.

import sys
input = sys.stdin.readline

 

도대체 무슨 차이인지 검색해보았다.

https://yeomss.tistory.com/120

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

input을 썼을 때 보다 더 빠른 수행 속도를 가진다고 한다.

 

# 구간 합 구하기 5
# N*N개의 수가 N*N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
# 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2가 주어진다.
# 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
origin = list()
result = list()

# 원본 배열 입력
for i in range(0, n):
    a = list(map(int, input().split()))
    origin.append(a)

# 합배열 생성
sum = [[0]*(n+1) for i in range(n+1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + origin[i - 1][j - 1]

# x1, y1, x2, y2 입력
for i in range(0, m):
    x1, y1, x2, y2 = map(int, input().split())
    result.append(sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1])

# 결과 출력
for i in range(0, m):
    print(result[i])

input = sys.stdin.readline() 으로 했을 때 컴파일 에러가 발생했고, 괄호를 빼면 제대로 동작한다.

무슨 차이인지 모르겠다..