파이선) 어두운 건 무서워 - BOJ (2D Array prefix sum, and 블로그의 방향성)

 

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

 

r, c, q = map(int, input().split())

arr = []

for _ in range(r):
    arr.append(list(map(int, input().split())))


dp = [[0 for _ in range(c+1)] for _ in range(r+1)]

# print(dp)

for i in range(1, r+1):
    for j in range(1, c+1):
        dp[i][j] = -dp[i-1][j-1] + dp[i][j-1] + dp[i-1][j] + arr[i-1][j-1]


for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())

    num = dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1]

    div = ((r2 - r1) + 1) * ((c2 - c1) + 1)

    print(num // div)

 

우선 누적합을 구해야한다.

누적합을 구하는 방식은 다음과 같다.

 

i,j번째는 바로 위쪽 값과 바로 왼쪽 값을 더한 후 대각선을 빼고 현재 자리수를 더한 값이다.

 

 

1	2	3
4	5	6
7	8	9

 

의 값이 있다.

 

코드와 같이 누적합을 5까지 구했을 때는 다음과 같다.

 

1	3	6
5	12

그럼 6의 자리인 2,3은 어떻게 구할까

12 + 6- 3 + 6(현재 자리값)으로 구할 수가 있다.

 

 

중복제거

 

왜 왼쪽 위 대각선을 빼는거지?

 

문득 그런 생각이 들었다.

 

이차원 배열 arr의 i,j의 누적값은 0,0에서부터 i,j까지의 누적합이라 볼 수가있다.

 

 

즉 오른쪽 사진의 58이란 값은 왼쪽의 분홍색 영역의 누적합과 같다.

 

위 사진의 4는 사진과 같은 누적합을 구한 값이고

 

18 또한 왼쪽 분홍색 영역의 누적합을 구한 것과 같다.

그럼 그 다음 줄로 넘어가보자.

그 다음줄의 첫번째 숫자인 9의 누적합 값은 무엇이될까?

0,0에서 9가 있는 1,0까지의 누적합은 0,0 +.1,1이된다.

 

 

17 또한 마찬가지이다.

0,0에서부터 1,1까지의 누적합을 계산한 것이 17이다.

하지만 우린 좀 더 쉽게 구할 수가 있다.

 

아까 바로 위 0,1이 0,0 +.0,0의 누적합이라 우리는 이미 계산을 끝냈고,

1,0은 0,0 +. 1,0이라는 계산을 이미 끝내놓았다.

즉, 바로 왼쪽 값 + 위의 누적값은 현재 위치의 누적합이 된다.

그러나 여기서 함정이 있다.

 

위 식을 나열하면 다음과 같다.

1,1 = 0,0 + 0,1 + 0,0 + 1,0

0,0이 두 번이나 중복이된다.

때문에 우리는 0,0의 값, 즉 왼쪽 대각선 위의 값을 빼주므로 완벽한 [i][j]의 누적값을 구할 수가 있다.

 

 

[i][j], [r][c]의 누적합

 

중복, 중복, 중복! 중복을 신경써야한다

 

 

다시 한 번 생각해보자

 

위 그림을 봐보자.

왼쪽의 이차원 배열의 누적합을 계산한 것이 오른쪽의 표이다.

편의상 왼쪽과 위에 0으로 한칸 더 만들어 두었다.

 

오른쪽 58은 왼쪽 분홍색 영역의 누적 합이된다.

 

 

마찬가지로 38 또한 왼쪽 분홍색 영역의 누적합이 된다.

 

그렇다면 2,2 - 4,4 영역의 누적합 등과 같은,

 

즉 위 사진과 같은 영역은 어떻게 구하면 될까?

 

우선 분홍색 네모칸 오른쪽 끝 "5"의 누적합을 살펴보자.

"5"가 위치한 자리의 누적합은 "106"이된다. 이 "106"의 값은 다음과 같은 영역의 누적합이다.

 

 

 

위 누적합에서 구하고자하는 부분은 다음과 같다.

 

즉, 초록색 영역의 누적합을 구하기 위해선 "5"자리의 누적합을 구한 다음 분홍색 영역의 값을 빼주면 구하고자 하는 누적합을 구할수가 있다.

 

쉽게 말하자면 다음과 같다.

 

 

---

 

끝으로 잠깐 끄적여보겠다.

 

지난 주, 주말에, 그리고 오늘 "커리어리"라는 플랫폼에 올라온 송요창 님의 "개발 블로그는 어떻게 써야할까?"를 읽어보았다.

 

-블로그는 자신의 경험과 지식을 다른 사람들과 공유하는 공간이며, 단순히 개인 공부 노트로 쓰는 것은 블로그의 목적에 맞지 않습니다.

-어려운 개념을 잘 정리하거나, 프로젝트에 활용한 경험을 공유하거나, 내부 원리에 대해 깊게 다루는 글은 글의 퀄리티가 높고, 다른 사람들에게 도움이 될 수 있습니다.

-글을 쓸 때는 읽는 사람을 배려해야 하며, 그림이나 문단, 스타일 등을 잘 활용하여 글의 가독성을 높혀야 합니다.

                                                                                                                                                                       -송요창 님의 글

 

위 말을 며칠동안 곱씹어보았다.

 

현재까지 내가 운영하는 이 블로그는 단순히 개인 공부를 정리하는, 사실 정리라기 보단 끄적임에 가까운 블로그였다.

단순히 내 블로그의 방문자가 없어서, 그리 쓸만한 지식을 게시하지 않아서라는 변명을 하고싶겠지만, 남들을 배려하지 않고 게시글의 퀄리티, 블로그 운영의 목적에 맞지 않으니 방문자 수가 늘어나지 않고 퀄리티와 방향성은 점차 떨어지게 되었다.

 

하루하루를 공부하며 그날 공부한 것에 대해 게시를 하는 것이 아닌 무언가 깨달음을 얻고 내게 도움이 되었던 지식들을 남들에게 공유하고자하는 블로그로 다시 태어나려한다.